1.4 Advanced Sorting1.3.3 Drawing Fractals1 Algorithms and Data Structures in Java1.4.1 Partitioning the Array

1.4 Advanced Sorting

The insertion sort algorithm presented is quadratic in the length of the array; it is therefore only practical for arrays of moderate size. There exist several more advanced sorting algorithms that are also applicable to large arrays; the most popular of them is  QuickSort which was discovered by the British computer scientist C.A.R. Hoare in 1962.

The basic idea of this algorithm is as follows. First, we choose an arbitrary array element as the  pivot element.

Later we will see that the choice of the pivot element may influence the efficiency of the algorithm.

QuickSort

Next, we decompose the array into two partitions: one partition only contains elements less than the pivot; the other partition only contains elements greater than or equal to the pivot. The partitioning proceeds by reordering the values in the array such that all elements of the first partition are to the left of the pivot which is to the left of all elements of the second partition.

QuickSort

Finally, we sort both partitions by recursive invocations of the algorithm. After the calls, both partitions are sorted; since the elements in the left partition are smaller than the pivot element which is smaller than or equal to the elements in the right partition, the whole array is sorted:

QuickSort

The base case of the recursion is reached with an array of length one or less (which is automatically sorted).

The following applet illustrates the QuickSort algorithm.

If you don't see the applet, your Browser does not support Java. Click here, to view a precomputed image.
Choose the Size of the array to be sorted and then either Step through the algorithm or let it Run. The markers left and right refer to the current range investigated; the marker pivot denotes the pivot element used in the partitioning. The markers leftScan and rightScan are used in the partitioning algorithm (see the next section).

Applet

The main structure of the algorithm is formalized by the following methods:

  static void quickSort(int[] a)
  {
    quickSort(a, 0, a.length-1);
  }
  
  // ------------------------------------------------
  // quickSort(a, left, right)
  // sort 'a' by the QuickSort algorithm
  // in the index range 'left..right'.
  //
  // Input:
  //   'a' is not null and has indices 'left..right'
  // Output:
  //   'a' has the same elements as the old 'a'.
  //   'a' is sorted in range 'left..right'
  // ------------------------------------------------
  static void quickSort(int[] a, int left, int right)
  {
    if (left >= right) return;
    int pos = partition(a, left, right);
    quickSort(a, left, pos-1);
    quickSort(a, pos+1, right);
  }

Here the method partition partitions the array as discussed above and returns the index pos of the pivot element. The recursive invocation therefore sort the array in index ranges that are strictly smaller than the original range.

While QuickSort is faster for large arrays, the insertion sort algorithm has less execution overhead for small arrays. It is therefore common practice to combine the strengths of both algorithms in the following way:

  static void quickSort(int[] a, int left, int right)
  {
    if (right-left < MINLEN) 
    {
      insertionSort(a, left, right);
      return;
    }
    int pos = partition(a, left, right);
    quickSort(a, left, pos-1);
    quickSort(a, pos+1, right);
  }

We apply (a generalized version of) the insertion sort algorithm in the base case of QuickSort to sort arrays that are not longer than MINLEN (say 10) elements. This is the quickest method to sort arrays in most environments.


© Wolfgang Schreiner; February 3, 2005

1.4 Advanced Sorting1.3.3 Drawing Fractals1 Algorithms and Data Structures in Java1.4.1 Partitioning the Array