Hide
Writing an article is easy - try our reStructured Text demo Join Siafoo Now or Learn More

Quick Sort Atom Feed 2

In Brief Quicksort is a fast, recursive, divide and conquer algorithm developed by Charles Antony Richard Hoare. It is believed to be the fastest sorting algorithm, in practice [Weiss1999].... more
Performance Bound Log Linear
Implementation Difficulty * * * * *
 1 function quicksort(array)
2
3 if len(array) <= 1
4 return array
5
6 pivot = pick_pivot(array) // Function to pick a pivot
7
8 array_1 = [] // Empty sequence
9 array_2 = [] // Empty sequence
10
11 foreach x in array
12 if x <= pivot
13 array_1.append(x)
14 else
15 array_2.append(x)
16
17 return quicksort(array_1) + pivot + quicksort(array_2) // Append the arrays
18

Quicksort is a fast, recursive, divide and conquer algorithm developed by Charles Antony Richard Hoare. It is believed to be the fastest sorting algorithm, in practice [Weiss1999].

Operation

This algorithm operates by choosing a pivot, then splitting the unsorted array into two sub-arrays along the pivot, where one of the sub-arrays contains the elements with a value less than the pivot and the other array contains the elements with a value greater than the pivot. After the sub arrays are sorted, they are joined and the resulting sequence is sorted. Although if the arrays are sorted in place, no joining is necessary.

There are two key differences between QuickSort and Merge Sort, in QuickSort the arrays are split along a pivot, not along the middle, and since the array can be sorted in-place, only enough memory for the unsorted sequence is needed.

For a rigorous mathematical definition and analysis of QuickSort, and for a good algorithm on performing the partition in place see [Cormen2001].

Choosing a Pivot

The easiest way to pick a pivot that will results in good performance is to select it at random. Never pick the first or last elements as a pivot because if the array is already sorted in forward or reverse order, the algorithm will operate with extremely poor performance.

Without knowing more about the distribution of the sequence values, one of the best ways to pick a pivot is to choose the median of three numbers in the array, [Weiss1999] recommends the median of the first, last and middle element of the array, as this should result in good performance for arrays already in sorted order.

Optimizations

A key optimization of Quicksort is to partition the array in place, this not only reduces the memory footprint and overhead caused by memory allocations but also removes the need to join the sorted sub-arrays.

Another optimization stems from the fact that Quicksort is not very efficient for small arrays ( < 10-20 elements). Thus it is common, and advised, to switch to a more efficient algorithm at a cutoff of around 10 or 20 elements, [Weiss1999] claims that this approach can result in a 15% performance boost. For an algorithm suitable for this purpose is Insertion Sort.

References

[Weiss1999](1, 2) Mark Allen Weiss. Data Structures & Algorithm Analysis in C++
[Cormen2001]Thomas H. Cormen, et al. Introduction To Algorithms, 2001

More Information

Quicksort is one of the most popular sorting algorithm, as such a query on your favorite search engine for Quicksort, will provide you with lots of information on the algorithm, it's performance and implemenation.

Another good starting point for QuickSort variants and implementations is the Wikpedia entry on QuickSort.

Implementations
A Scala implementation of Quick Sort using imperative programming (i.e. what you are used to). Compare this implementation to the much shorter functional version
A simple implementation of Quicksort in Python. I'll add a more intelligent pivot-picker soon.
A Scala implementation of Quick Sort using functional programming techniques. Compare this clean and delicious implementation to the considerably longer imperative version
Can chose different pivot types by setting pivot_type