1.4.1 Partitioning the Array1.4 Advanced Sorting1.4 Advanced Sorting1.5 Dynamic Data Structures

1.4.1 Partitioning the Array

We are now going to develop the partitioning method

  // ----------------------------------------------------------
  // i = partition(a, left, right)
  // 'i' is the index of the pivot element that has decomposed
  //  array 'a' into two partitions left/right to the pivot
  //
  // Input:
  //   'a' is not null and has index range 'left..right'.
  // Output:
  //   'a' is unchanged outside the index range 'left..right'
  //   and reordered within 'left..right' such that
  //   'a[left..i-1]' only holds elements < 'a[i]' and
  //   'a[i+1..right]' only holds elements >= 'a[i]'
  // ----------------------------------------------------------
  static int partition(int[] a, int left, int right) { ... }

Our first problem in this development is the choice of the pivot element from the array elements. While the algorithm returns for any choice a correct solution, the performance can be negatively affected by poor choices. For instance, if the input array is already sorted, it is a bad idea to choose a[left] as the pivot element. In this case, one partition has size 0 while the other partition has size n-1 (where n is the length of the array). Sorting the second partition again yields a partition of size 0 and another partition of size n-2 and so on. In total, the QuickSort algorithm will therefore execute n+(n-1)+(n-2)+...+1  n2 steps, i.e., it will show the same quadratic behavior as the insertion sort algorithm.

However, if we choose the pivot element such that it decomposes the array into partitions of approximately same size (n/2), the algorithm will take about n+2*(n/2 + 2*(n/4 + ...+ 2 * 1)) approx n * log2 n steps. For instance, an array of length 8192 can be sorted by QuickSort in about 106000 steps which is a drastic improvement over quadratic sorting algorithms like insertion sort (which requires about 16 million steps). Actually, one can prove that n * log2 n is a lower bound for the time complexity of the sorting problem, i.e., there do not exist any algorithms that are essentially faster than QuickSort.

The sorting problem is of complexity n * log2 n.
.

For choosing a good pivot element, there exist several strategies. One approach is to pick a random element, but the computation of random numbers is costly. Another approach is to take the median of three fixed values, for instance of a[left], a[right], and a[(left+right)/2]. Another choice is just to take the element a[(left+right)/2] in the middle of the array; it is practically very unlikely that the value distribution in the array is such that this choice lets the algorithm degenerate to quadratic behavior. The code of partition therefore starts as follows:

  final int pos = (left+right)/2;
  final int pivot = a[pos];

Once the pivot element is chosen we can give its place to a[right]

  a[pos] = a[right];

such that we only have to partition the array in the range left..right-1. At the end of the algorithm, we will store the pivot back to the array at an appropriate partition.

The basic idea of the partitioning is to have two indices l and r such that a[l..r] represents the part of the array which remains to be investigated:

  int l = left;
  int r = right-1;

During the execution, the array range a[left..l-1] will hold only elements less than the pivot (and thus is part of the first partition) and a[r+1..right-1] will hold only elements greater than or equal to the pivot (and thus is part of the second partition).

Scanning

We start by scanning the array from the left looking for an element a[l] which does not any more belong to the first partition:
  while (l <= r && a[l] < pivot)
    l = l+1;

Likewise, we scan the array from the right looking for an element a[r] which does not any more belong to the second partition:

  while (l <= r && a[r] >= pivot)
    r = r-1;

If we have found such elements, we swap a[l] and a[r] which extends the left partition by one element and the right partition by one element:

  int t = a[l];
  a[l] = a[r];
  a[r] = t;
  l = l+1;
  r = r-1;

This process continues until the "scanning from the left" crosses the "scanning from the right" at a particular index l; this index thus represents the position to be taken by the pivot element between the first partition and the second partition. Therefore we exchange a[l] with the pivot element stored at a[right] and return l to the caller.

  if (l > r) 
    {
      a[right] = a[l];
      a[l] = pivot;
      return l;
    }

The following applet illustrates the partitioning 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 partitioned and then either Step through the algorithm or let it Run. The markers leftScan and rightScan describe the range already scanned.

Applet

The complete code for the partitioning method is thus as follows:

  static int partition(int[] a, int left, int right)
  {
    final int pos = (left+right)/2;
    final int pivot = a[pos];
    a[pos] = a[right];

    int l = left;
    int r = right-1;

    while (true)
    {
      while (l <= r && a[l] < pivot)
        l = l+1;
      while (l <= r && a[r] >= pivot)
        r = r-1;

      if (l > r) 
      {
        a[right] = a[l];
        a[l] = pivot;
        return l;
      }

      int t = a[l];
      a[l] = a[r];
      a[r] = t;
      l = l+1;
      r = r-1;
    }
  }

In this method, only the first line

  final int pos = ...

has to be changed in order to apply another strategy for choosing the pivot element.


© Wolfgang Schreiner; February 3, 2005

1.4.1 Partitioning the Array1.4 Advanced Sorting1.4 Advanced Sorting1.5 Dynamic Data Structures