Beginning Java Data Structures and Algorithms

Understanding Quick Sort

Quick sort is a big improvement over bubble sort. This sorting technique was developed by British computer scientist Tony Hoare. The algorithm works in three main steps:

1. Select a pivot
2. Partition the list so that elements on the left of the pivot are less than the value of the pivot and the ones on the right are greater
3. Repeat steps 1 and 2 on the left and right parts separately

Since recursion is required for quick sort, we will begin this section by giving an example of recursion. Later, we will see how the partitioning in the quick sort algorithm works, and in the end, we will put the recursion techniques to use in the final part.