How Does the Quicksort Technique in Java Work?
Here, you find out how one of the most commonly used sorting techniques in Java actually works. This technique is called Quicksort, and it’s a very ingenious use of recursion.
For most of us, figuring out how sorting algorithms such as Quicksort work is merely an intellectual exercise. The Java API has sorting already built in.
The Quicksort technique sorts an array of values by using recursion. Its basic steps are thus:
Pick an arbitrary value that lies within the range of values in the array.
This value is the pivot point. The most common way to choose the pivot point is to simply pick the first value in the array. Folks have written doctoral degrees on more-sophisticated ways to pick a pivot point that results in faster sorting. Stick with using the first element in the array.
Rearrange the values in the array so that all the values that are less than the pivot point are on the left side of the array and all the values that are greater than or equal to the pivot point are on the right side of the array.
The pivot value indicates the boundary between the left side and the right side of the array. It probably won’t be dead center, but that doesn’t matter. This step is called partitioning, and the left and right sides of the arrays are partitions.
Now treat each of the two sections of the array as a separate array, and start over with Step 1 for that section.
That’s the recursive part of the algorithm.
The hardest part of the Quicksort algorithm is the partitioning step, which must rearrange the partition so that all values that are smaller than the pivot point are on the left and all elements that are larger than the pivot point are on the right. Suppose that the array has these ten values:
38 17 58 22 69 31 88 28 86 12
Here the pivot point is 38, and the task of the partitioning step is to rearrange the array to something like this:
17 12 22 28 31 38 88 69 86 58
Notice that the values are still out of order. The array, however, has been divided around the value 38: All values that are less than 38 are to the left of 38, and all values that are greater than 38 are to the right of 38.
Now you can divide the array into two partitions at the value 38 and repeat the process for each side. The pivot value itself goes with the left partition, so the left partition is this:
17 12 22 28 31 38
This time, the partitioning step picks 17 as the pivot point and rearranges the elements as follows:
12 17 22 28 31 38
As you can see, this portion of the array is sorted now. Unfortunately, Quicksort doesn’t realize that at this point, so it takes a few more recursions to be sure. But that’s the basic process.