Sorting algorithms

Quicksort is one of the fastest and simplest sorting algorithms [Hoa 62]. It works recursively by a divide-and-conquer strategy.

Idea

First, the sequence to be sorted a is partitioned into two parts, such that all elements of the first part b are less than or equal to all elements of the second part c (divide). Then the two parts are sorted separately by recursive application of the same procedure (conquer). Recombination of the two parts yields the sorted sequence (combine). Figure 1 illustrates this approach.

The first step of the partition procedure is choosing a comparison element x. All elements of the sequence that are less than x are placed in the first part, all elements greater than x are placed in the second part. For elements equal to x it does not matter into which part they come. In the following algorithm it may also happen that an element equal to x remains between the two parts.

Input:

sequence a₀, ..., a_n-1 with n elements

Output:

permutation of the sequence such that all elements a₀, ..., a_j are less than or equal to all elements a_i, ..., a_n-1   (i > j)

Method:

1. choose the element in the middle of the sequence as comparison element x
2. let i = 0 and j = n-1
3. while i ≤ j
1. search for the first element a_i which is greater than or equal to x
2. search for the last element a_j which is less than or equal to x
3. if i ≤ j
1. exchange a_i and a_j
2. let i = i+1 and j = j-1

After partitioning the sequence, quicksort treats the two parts recursively by the same procedure. The recursion ends whenever a part consists of one element only.

Program

The following Java program implements quicksort. The comparison element x is chosen as the element in the mid between lo and hi ¹).

Analysis

The best-case behavior of the quicksort algorithm occurs when in each recursion step the partitioning produces two parts of equal length. In order to sort n elements, in this case the running time is in Θ(n log(n)). This is because the recursion depth is log(n) and on each level there are n elements to be treated (Figure 2 a).

The worst case occurs when in each recursion step an unbalanced partitioning is produced, namely that one part consists of only one element and the other part consists of the rest of the elements (Figure 2 c). Then the recursion depth is n-1 and quicksort runs in time Θ(n²).

In the average case a partitioning as shown in Figure 2 b is to be expected.

The choice of the comparison element x determines which partition is achieved. Suppose that the first element of the sequence is chosen as comparison element. This would lead to the worst case behavior of the algorithm when the sequence is initially sorted. Therefore, it is better to choose the element in the middle of the sequence as comparison element.

Even better would it be to take the n/2-th greatest element of the sequence (the median). Then the optimal partition is achieved. Actually, it is possible to compute the median in linear time [AHU 74]. This variant of quicksort would run in time O(n log(n)) even in the worst case.

However, the beauty of quicksort lies in its simplicity. And it turns out that even in its simple form quicksort runs in O(n log(n)) on the average. Moreover, the constant hidden in the O-notation is small. Therefore, we trade this for the (rare) worst case behavior of Θ(n²).

Conclusions

Quicksort turns out to be the fastest sorting algorithm in practice. It has a time complexity of Θ(n log(n)) on the average. However, in the (very rare) worst case quicksort is as slow as Bubblesort, namely in Θ(n²). There are sorting algorithms with a time complexity of O(n log(n)) even in the worst case, e.g. Heapsort and Mergesort. But on the average, these algorithms are by a constant factor slower than quicksort.

It is possible to obtain a worst case complexity of O(n log(n)) with a variant of quicksort (by choosing the median as comparison element). But this algorithm is on the average and in the worst case by a constant factor slower than Heapsort or Mergesort; therefore, it is not interesting in practice.

References

Quicksort was originally published by C.A.R. Hoare [Hoa 62].

[AHU 74]   A.V. Aho, J.E. Hopcroft, J.D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley (1974)

[Hoa 62]   C.A.R. Hoare: Quicksort. Computer Journal, Vol. 5, 1, 10-15 (1962)

[CLRS 01]   T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein: Introduction to Algorithms. 2nd edition, The MIT Press (2001)

[Sed 03]   R. Sedgewick: Algorithms in Java, Parts 1-4. 3rd edition, Addison-Wesley (2003)

Web

[Web 1]   http://www.bluffton.edu/~nesterd/java/SortingDemo.html   Simulation of quicksort and other sorting algorithms