As one of the more advanced sorting algorithms, you might think that the Quicksort Algorithm is steeped in complicated theoretical background, but this is not so. Like Insertion Sort, this algorithm has a fairly simple concept at the core, but is made complicated by the constraints of the array structure. The basic concept is to pick one of the elements in the array as a pivot value around which the other elements will be rearranged. Everything less than the pivot is moved left of the pivot (into the left partition). Similarly, everything greater than the pivot goes into the right partition. At this point each partition is recursively quicksorted. The Quicksort algorithm is fastest when the median of the array is chosen as the pivot value. That is because the resulting partitions are of very similar size. Each partition splits itself in two and thus the base case is reached very quickly. In practice, the Quicksort algorithm becomes very slow when the array passed to it is already close to being sorted. Because there is no efficient way for the computer to find the median element to use as the pivot, the first element of the array is used as the pivot. So when the array is almost sorted, Quicksort doesn't partition it equally. Instead, the partitions are lopsided like in Figure 2. This means that one of the recursion branches is much deeper than the other, and causes execution time to go up. Thus, it is said that the more random the arrangement of the array, the faster the Quicksort Algorithm finishes. Figure 1: The ideal Quicksort on a random array. Figure 2: Quicksort on an already sorted array. These are the steps taken to sort an array using QuickSort: Elements in red indicate swaps. Elements in blue indicate comparisons. Special commentary is in green. 3 1 4 5 9 2 6 8 7 Calling quickSort on elements 0 to 8 Definitions: a "small" element is one whose value is less than or equal to the value of the pivot. Likewise, a "large" element is one whose value is larger than that of the pivot. At the beginning, the entire array is passed into the quicksort function and is essentially treated as one large partition. At this time, two indices are initialized: the left-to-right search index, An implementation of the algorithm is shown below: public void quickSort(int array[]) // pre: array is full, all elements are non-null integers // post: the array is sorted in ascending order { quickSort(array, 0, array.length - 1); // quicksort all the elements in the array } public void quickSort(int array[], int start, int end) { int i = start; // index of left-to-right scan int k = end; // index of right-to-left scan if (end - start >= 1) // check that there are at least two elements to sort { int pivot = array[start]; // set the pivot as the first element in the partition while (k > i) // while the scan indices from left and right have not met, { while (array[i] <= pivot && i <= end && k > i) // from the left, look for the first i++; // element greater than the pivot while (array[k] > pivot && k >= start && k >= i) // from the right, look for the first k--; // element not greater than the pivot if (k > i) // if the left seekindex is still smaller than swap(array, i, k); // the right index, swap the corresponding elements } swap(array, start, k); // after the indices have crossed, swap the last element in // the left partition with the pivot quickSort(array, start, k - 1); // quicksort the left partition quickSort(array, k + 1, end); // quicksort the right partition } else // if there is only one element in the partition, do not do any sorting { return; // the array is sorted, so exit } } public void swap(int array[], int index1, int index2) // pre: array is full and index1, index2 < array.length // post: the values at indices 1 and 2 have been swapped { int temp = array[index1]; // store the first value in a temp array[index1] = array[index2]; // copy the value of the second into the first array[index2] = temp; // copy the value of the temp into the second } Written by Eugene Jitomirsky. Improved code courtesy of Pavel. |