Quick Sort

A quick sort works as follows: The algorithm selects an element, called the pivot, in the array. It divides the array into two parts, so that all the elements in the first part are less than or equal to the pivot and all the elements in the second part are greater than the pivot. The quick sort algorithm is then recursively applied to the first part and then the second part. The quick sort algorithm, developed by C.A.R. Hoare in 1962, is described in code below:

public static void quickSort(int[] list) {
if (list.length > 1) {
select a pivot;
partition list into list1 and list2 such that
all elements in list1 <= pivot and
all elements in list2 > pivot;
quickSort(list1);
quickSort(list2);
}
}

Each partition places the pivot in the right place. The selection of the pivot affects the performance of the algorithm. Ideally, the algorithm should choose the pivot that divides the two parts evenly. For simplicity, assume the first element in the array is chosen as the pivot.

Figure below illustrates how to sort an array (5 2 9 3 8 4 0 1 6 7) using quick sort. Choose the first element, 5, as the pivot. The array is partitioned into two parts, as shown in Figure below (b). The highlighted pivot is placed in the right place in the array. Apply quick sort on two partial arrays (4 2 1 3 0) and then (8 9 6 7). The pivot 4 partitions (4 2 1 3 0) into just one partial array (0 2 1 3), as shown in Figure below (c). Apply quick sort on (0 2 1 3). The pivot 0 partitions it into just one partial array (2 1 3), as shown in Figure below (d). Apply quick sort on (2 1 3). The pivot 2 partitions it into (1) and (3), as shown in Figure below (e). Apply quick sort on (1). Since the array contains just one element, no further partition is needed.

The quick sort algorithm is implemented in code below. There are two overloaded quickSort methods in the class. The first method (line 4) is used to sort an array. The second is a helper method (line 8) that sorts a partial array with a specified range.

package demo;

public class QuickSort {
    public static void quickSort(int[] list) {
        quickSort(list, 0, list.length - 1);
    }

    public static void quickSort(int[] list, int first, int last) {
        if(last > first) {
            int pivotIndex = partition(list, first, last);
            quickSort(list, first, pivotIndex - 1);
            quickSort(list, pivotIndex + 1, last);
        }
    }

    /** Partition the array list[first..last] */
    public static int partition(int[] list, int first, int last) {
        int pivot = list[first]; // Choose the first element as the pivot
        int low = first + 1; // Index for forward search
        int high = last; // Index for backward search

        while(high > low) {
            // Search forward from left
            while(low <= high && list[low] <= pivot)
                low++;

            // Search backward from right
            while(low <= high && list[high] > pivot)
                high--;

            // Swap two elements in the list
            if(high > low) {
                int temp = list[high];
                list[high] = list[low];
                list[low] = temp;
            }
        }

        while(high > first && list[high] >= pivot)
            high--;

        // Swap pivot with list[high]
        if(pivot > list[high]) {
            list[first] = list[high];
            list[high] = pivot;
            return high;
        }
        else {
            return first;
        }
    }

    public static void main(String[] args) {
        int[] list = {2, 3, 2, 5, 6, 1, -2, 3, 14, 12};
        quickSort(list);
        for(int i = 0; i < list.length; i++)
            System.out.print(list[i] + " ");
    }

}

The partition method (lines 17–51) partitions the array list[first..last] using the pivot. The first element in the partial array is chosen as the pivot (line 18). Initially low points to the second element in the partial array (line 19) and high points to the last element in the partial array (line 20).

Starting from the left, the method searches forward in the array for the first element that is greater than the pivot (lines 24–25), then searches from the right backward for the first element in the array that is less than or equal to the pivot (lines 28–29). It then swaps these two elements and repeats the same search and swap operations until all the elements are searched in a while loop (lines 22–37).

The method returns the new index for the pivot that divides the partial array into two parts if the pivot has been moved (line 46). Otherwise, it returns the original index for the pivot (line 49).

Figure below illustrates how to partition an array (5 2 9 3 8 4 0 1 6 7). Choose the first element, 5, as the pivot. Initially low is the index that points to element 2 and high points to element 7, as shown in Figure below (a). Advance index low forward to search for the first element (9) that is greater than the pivot and move index high backward to search for the first element (1) that is less than or equal to the pivot, as shown in Figure below (b). Swap 9 with 1, as shown in Figure below (c). Continue the search and move low to point to element 8 and high to point to element 0, as shown in Figure below (d). Swap element 8 with 0, as shown in Figure below (e). Continue to move low until it passes high, as shown in Figure below (f). Now all the elements are examined. Swap the pivot with element 4 at index high. The final partition is shown in Figure below (g). The index of the pivot is returned when the method is finished.

To partition an array of n elements, it takes n comparisons and n moves in the worst case. Thus, the time required for partition is O(n).

In the worst case, the pivot divides the array each time into one big subarray with the other array empty. The size of the big subarray is one less than the one before divided. The algorithm requires (n - 1) + (n - 2) + ... + 2 + 1 = O(n^2) time.

In the best case, the pivot divides the array each time into two parts of about the same size. Let T(n) denote the time required for sorting an array of n elements using quick sort. Thus,

Similar to the merge sort analysis, T(n) = O(n logn).

On the average, the pivot will not divide the array into two parts of the same size or one empty part each time. Statistically, the sizes of the two parts are very close. Therefore, the average time is O(n logn). The exact average-case analysis is beyond the scope of this book.

Both merge sort and quick sort employ the divide-and-conquer approach. For merge sort, the bulk of the work is to merge two sublists, which takes place after the sublists are sorted. For quick sort, the bulk of the work is to partition the list into two sublists, which takes place
before the sublists are sorted. Merge sort is more efficient than quick sort in the worst case, but the two are equally efficient in the average case. Merge sort requires a temporary array for sorting two subarrays. Quick sort does not need additional array space. Thus, quick sort is more space efficient than merge sort.