Quicksort

From open-encyclopedia.com - the free encyclopedia.

Quicksort is a well-known sorting algorithm developed by C. A. R. Hoare that, on average, needs Θ(n log n) comparisons to sort n items, while requiring Θ(n²) comparisons in the worst-case.

It is based on the divide and conquer method.

Quicksort's inner loop is such that it is usually easy to implement very efficiently on most computer architectures, which makes it significantly faster in practice than other Θ(n log n) algorithms that can sort in place or nearly so in the average case (recursively-implemented quicksort is not, as is sometimes regarded, an in-place algorithm, requiring Θ(log n) on average, and Θ(n) in the worst case, of stack space for recursion.)

Performance and algorithm details

Because of its good average performance and simple implementation, Quicksort is one of the most popular sorting algorithms in use. It is an unstable sort in that it doesn't preserve any ordering that is already between elements of the same value. Quicksort's worst-case performance is Θ(n²); much worse than some other sorting algorithms such as heapsort or merge sort. However, if pivots are chosen randomly, most bad choices of pivots are unlikely; the worst-case has only probability 1/n! of occurring.

The Quicksort algorithm uses a recursive divide and conquer strategy to sort a list. The steps are:

• Pick a pivot element from the list.
• Reorder the list so that all elements less than the pivot precede all elements greater than the pivot. This means that the pivot is in its final place; the algorithm puts at least one element in its final place on each pass over the list. This step is commonly referred to as "partitioning".
• Recursively sort the sub-list of elements less than the pivot and the sub-list of elements greater than the pivot. If one of the sub-lists is empty or contains one element, it can be ignored.

In pseudocode, the complete algorithm in its simplest form is:

The following is wikicode, a proposed pseudocode for use in many articles:

 function partition(a, left, right, pivotIndex)
     pivotValue := a[pivotIndex]
     swap(a[pivotIndex], a[right]) // Move pivot to end
     storeIndex := left
     for i from left to right-1
         if a[i] <= pivotValue
             swap(a[storeIndex], a[i])
             storeIndex := storeIndex + 1
     swap(a[right], a[storeIndex]) // Move pivot to its final place
     return storeIndex
 
 function quicksort(a, left, right)
     if right > left
         select a pivot value a[pivotIndex]
         pivotNewIndex := partition(a, left, right, pivotIndex)
         quicksort(a, left, pivotNewIndex-1)
         quicksort(a, pivotNewIndex+1, right)

The inner loop which performs the partition is amenable to optimization, for two main reasons:

• All comparisons are being done with a single pivot value, which can be stored in a register.
• The list is being traversed sequentially, which for arrays produces very good locality of reference and cache behavior.

This is one reason why Quicksort is often the fastest sorting algorithm, at least on average over all inputs.

The most crucial problem of Quicksort is the choice of pivot element. A naïve implementation of Quicksort, like the ones below, will be terribly inefficient for certain inputs. For example, if the pivot always turns out to be the smallest element in the list, then Quicksort degenerates to Selection sort with Θ(n²) running time. A secondary problem is the recursion depth. This becomes linear, and the stack requires Θ(n) extra space.

Note that the partition procedure only requires the ability to traverse the list sequentially; therefore, quicksort is not confined to operating on arrays (it can be used, for example, on linked lists). Choosing a good pivot, however, benefits from random access, as we will see.

Choosing a better pivot

The worst-case behavior of quicksort is not merely a theoretical problem. When quicksort is used in web services, for example, it is possible for an attacker to deliberately exploit the worst case performance and choose data which will cause a slow running time or maximize the chance of running out of stack space. See competitive analysis for more discussion of this issue.

Sorted or partially sorted data is quite common in practice and the naïve implementation which selects the first element as the pivot does poorly with such data. To avoid this problem the middle element can be used. This works well in practice but attacks can cause worst-case performance.

A better optimization can be to select the median element of the first, middle and last elements as the pivot. Adding two randomly selected elements resists chosen data attacks, more so if a cryptographically sound random number generator is used to reduce the chance of an attacker predicting the "random" elements. The use of the fixed elements reduces the chance of bad luck causing a poor pivot selection for partially sorted data when not under attack. These steps increase overhead, so it may be worth skipping them once the partitions grow small and the penalty for poor pivot selection drops.

Finding the true median value and using it as the pivot can be done if the number of elements is large enough to make it necessary but this is seldom done in practice.

Partitioning concerns

As virtually all of the quicksort computation time is spent partitioning, a good partitioning implementation is important. In particular, if all of the elements being partitioned are equal, the above partition algorithm degenerates into the worst case, needlessly swapping identical elements and returning the worst possible pivot. This becomes a serious problem in any datasets which contain many equal elements, as many of the 'bottom tier' of partitions will become uniform.

A good variation in such cases is to test separately for equal elements and store these in a 'fat pivot' in the center of the partition. An implementation of this variation implemented in C is shown below. Another, easier alternative is to avoid recursing if the left-most and right-most elements are equal after partitioning.

Other optimizations

Another optimization is to switch to a different sorting algorithm once the list becomes small, perhaps ten or less elements. Selection sort might be inefficient for large data sets, but it is often faster than Quicksort on small lists.

One widely used implementation of quicksort, that in the 1997 Microsoft C library, used a cutoff of 8 elements before switching to insertion sort, asserting that testing had shown that to be a good choice. It used the middle element for the partition value, asserting that testing had shown that the median of three algorithm did not, in general, increase performance.

Sedgewick (1978) suggested an enhancement to the use of simple sorts for small numbers of elements, which reduced the number of instructions required by postponing the simple sorts until the quicksort had finished, then running an insertion sort over the whole array. This is effective because insertion sort requires only O(kn) time to sort an array where every element is less than k places from its final position.

LaMarca and Ladner (1997) consider "The Influence of Caches on the Performance of Sorting", a very significant issue in microprocessor systems with multi-level caches and high cache miss times. They conclude that while the Sedgewick optimization decreases the number of instructions, it also decreases locality of cache references and worsens performance compared to doing the simple sort when the need for it is first encountered. However, the effect was not dramatic and they suggested that it was starting to become more significant with more than 4 million 64 bit float elements. Greater improvement was shown for other sorting types.

Because recursion requires additional memory, Quicksort has been implemented in a non-recursive, iterative form. This has the advantage of predictable memory use regardless of input, and the disadvantage of considerably greater code complexity. Those considering iterative implementations of quicksort would do well to also consider introsort or heapsort instead.

A simple alternative for reducing Quicksort's memory consumption uses true recursion only on the smaller of the two sublists and tail recursion on the larger. This limits the additional storage of Quicksort to O(log n). The procedure quicksort in the preceding pseudocode would be rewritten as

 function quicksort(a, left, right)
     while right > left
         select a pivot value a[pivotIndex]
         pivotNewIndex := partition(a, left, right, pivotIndex)
         if (pivotNewIndex-1) - left < right - (pivotNewIndex+1)
             quicksort(a, left, pivotNewIndex-1)
             left  := pivotNewIndex+1
         else
             quicksort(a, pivotNewIndex+1, right)
             right := pivotNewIndex-1

Introsort optimization

Main article: Introsort

An optimization of quicksort which is becoming widely used is introspective sort, often called introsort. This starts with quicksort and switches to heapsort when the recursion depth exceeds a preset value. This overcomes the overhead of increasingly complex pivot selection techniques while ensuring O(n log n) worst-case performance. Musser reported that on a median-of-3 killer sequence of 100,000 elements running time was 1/200th that of median-of-3 quicksort. Musser also considered the effect of Sedgewick's delayed small sorting on caches, reporting that it could double the number of cache misses when used on arrays, but its performance with double-ended queues was significantly better. See introsort for more details.

Competitive sorting algorithms

The most direct competitor of Quicksort is heapsort. Heapsort is typically somewhat slower than Quicksort, but the worst-case running time is always O(n log n). Quicksort is usually faster, though there remains the chance of worst case performance except in the introsort variant. If it's known in advance that heapsort is going to be necessary, using it directly will be faster than waiting for introsort to switch to it. Heapsort also has the important advantage of using only constant additional space (heapsort is in-place), whereas even the best variant of Quicksort uses O(log n) space. However, heapsort requires efficient random access to be practical.

Quicksort is a space-optimized version of the binary tree sort. Instead of inserting items sequentially into an explicit tree, Quicksort organizes them concurrently into a tree that is implied by the recursive calls. The algorithms make exactly the same comparisons, but in a different order.

Relationship to selection

A simple selection algorithm, which chooses the kth smallest of a list of elements, works nearly the same as quicksort, except instead of recursing on both sublists, it only recurses on the sublist which contains the desired element. This small change lowers the average complexity to linear or O(n) time. A variation on this algorithm brings the worst-case time down to O(n) (see selection algorithm for more information).

Conversely, once we know a worst-case O(n) selection algorithm is available, we can use it to find the ideal pivot (the median) at every step of Quicksort, producing a variant with worst-case O(n log n) running time. In practical implementations, however, this variant is considerably slower on average.

Sample implementations

Main article: Quicksort implementations

Here we demonstrate a number of quicksort implementations in various languages. We show only some of the most popular or unique ones here; for additional implementations, see the article quicksort implementations.

C

void sort(int array[], int begin, int end) {
   if (end > begin) {
      int pivot = array[begin];
      int l = begin + 1;
      int r = end;
      while(l < r) {
         if (array[l] <= pivot) {
            l++;
         } else {
            r--;
            swap(array[l], array[r]); 
         }
      }
      l--;
      swap(array[begin], array[l]);
      sort(array, begin, l);
      sort(array, r, end);
   }
}

C++

#include <algorithm>
#include <iterator>
#include <functional>

template <typename T>
void sort(T begin, T end) {
    if (begin != end) {
        T middle = partition (begin, end, bind2nd(
                less<iterator_traits<T>::value_type>(), *begin));
        sort (begin, middle);
        sort (max(begin + 1, middle), end);
    }
}

Java

This example also demonstrates a generic quicksort, rather than just one on a set of integers.

import java.util.Comparator;
import java.util.Random;

public class Quicksort {
    public static final Random RND = new Random();	
    private void swap(Object[] array, int i, int j) {
	Object tmp = array[i];
	array[i] = array[j];
	array[j] = tmp;
    }
    private int partition(Object[] array, int begin, int end, Comparator cmp) {
	int index = begin + RND.nextInt(end - begin + 1);
	Object pivot = array[index];
	swap(array, index, end);	
	for (int i = index = begin; i < end; ++ i) {
	    if (cmp.compare(array[i], pivot) <= 0) {
		swap(array, index++, i);
	    }
        }
	swap(array, index, end);	
	return (index);
    }
    private void qsort(Object[] array, int begin, int end, Comparator cmp) {
	if (end > begin) {
	    int index = partition(array, begin, end, cmp);
	    qsort(array, begin, index - 1, cmp);
	    qsort(array, index + 1,  end,  cmp);
        }
    }
    public void sort(Object[] array, Comparator cmp) {
	qsort(array, 0, array.length - 1, cmp);
    }
}

Python

def partition(array, begin, end, cmp):
    while begin < end:
         while begin < end:
            if cmp(array[begin], array[end]):
                (array[begin], array[end]) = (array[end], array[begin])
                break
            end -= 1
         while begin < end:
            if cmp(array[begin], array[end]):
                (array[begin], array[end]) = (array[end], array[begin])
                break
            begin += 1
    return begin

def sort(array, cmp=lambda x, y: x > y, begin=None, end=None):
    if begin is None: begin = 0
    if end   is None: end   = len(array)
    if begin < end:
        i = partition(array, begin, end-1, cmp)
        sort(array, cmp, begin, i)
        sort(array, cmp, i+1, end)

Joy

 DEFINE sort == [small][]
                [uncons [>] split]
                [[swap] dip cons concat] binrec .

Haskell

  sort :: (Ord a)   => [a] -> [a]
  
  sort []           = []
  sort (pivot:rest) = sort [y | y <- rest, y < pivot]
                      ++ [pivot] ++ 
                      sort [y | y <- rest, y >=pivot]

Prolog

append([], L, L).
append([H | L1], L2, [H | Result]) :- append(L1, L2, Result).

partition([], _, [], []).
partition([H | T], X, [H | Left], Right) :- H =< X, partition(T, X, Left, Right).
partition([H | T], X, Left, [H | Right]) :- H > X, partition(T, X, Left, Right).

qsort([],[]).
qsort([H | Tail], Sorted) :-
        partition(Tail, H, Left, Right),
        qsort(Left, SortedLeft),
        qsort(Right, SortedRight),
        append(SortedLeft, [X | SortedRight], Sorted).

External links

• animated Quicksort

References

• Hoare, C. A. R. "Partition: Algorithm 63," "Quicksort: Algorithm 64," and "Find: Algorithm 65." Comm. ACM 4, 321-322, 1961
• R. Sedgewick. Implementing quicksort programs, Communications of the ACM, 21(10):847857, 1978.
• David Musser. Introspective Sorting and Selection Algorithms, Software Practice and Experience vol 27, number 8, pages 983-993, 1997
• A. LaMarca and R. E. Ladner. "The Influence of Caches on the Performance of Sorting." Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997. pp. 370-379.

de:Quicksort es:Quicksort he:מיון מהיר ja:クイックソート pl:Sortowanie szybkie pt:Quicksort fr:Tri rapide nl:Quicksort