License Creative Commons Attribution Share Alike 3.0-US
##### Keywords
algorithm (8) quicksort (5) sort (5)
##### Permissions
Viewable by Everyone
Editable by All Siafoo Users
Stay up to dateembedded code automagically updates, each snippet and article has a feed

# Quick Sort 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
 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 sequence10 11     foreach x in array12         if x <= pivot13             array_1.append(x)14         else15             array_2.append(x)16 17     return quicksort(array_1) + pivot + quicksort(array_2) // Append the arrays18  `

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