Quick Sort in Java

Quick Sort is a divide and conquer algorithm which was developed by Tony Hoare in 1960.

Quick Sort first divides a large list into two smaller sub-lists: the low elements and the high elements and then recursively sort the sub-lists.

The steps are:

1. Pick an element, called a pivot, from the list.
2. Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
3. Recursively apply the above steps to the sub-list of elements with smaller values and separately the sub-list of elements with greater values.

Below Figure 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 (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 (c). Apply quick sort on (0 2 1 3). The pivot 0 partitions it to just one partial array (2 1 3), as shown in Figure (d). Apply quick sort on (2 1 3). The pivot 2 partitions it to (1) and (3), as shown in Figure (e). Apply quick sort on (1). Since the array contains just one element, no further partition is needed. 

Quick Sort Illustration

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

QuickSort.java

public class QuickSort {

       public static void quickSort(int[] list) {

              quickSort(list, 0, list.length - 1);

       }

       private 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] */

       private 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;

              }

       }

       /** A test method */

       public static void main(String[] args) {

              int[] list = { 5, 2, 9, 3, 8, 4, 0, 1, 6, 7 };

              quickSort(list);

              for (int i = 0; i < list.length; i++)

                     System.out.print(list[i] + " ");

       }

}

  

The output of this program is:

   0 1 2 3 4 5 6 7 8 9


Reference(s): 

http://en.wikipedia.org/wiki/Quicksort

Introduction to JAVA by Y. Daniel Liang