Have an Android phone?

Try our new game!

Quicksort algorithm

Redirected from Quicksort

Quicksort. The pivot is highlighted in red, the current sorting area is shaded and the recently swapped values highlighted in green. The sorting regions from the stack of the recursive calls is painted on the left. The current region is highlighted in red. The region on that partitioning will also be recursively is highlighted in blue. As it is depth first, not breath first iteration, the blue region is not sorted immediately after the red region.
Quicksort algorithm is a well-known sorting algorithm that, on average, makes comparisons to sort n items. In the worst case, it makes comparisons, though in correct implementations this behavior is rare[1]. Java library provides a standard way of sorting Arrays with Arrays.sort() that uses the algorithm, closely derived from Quicksort.

Advantages

  • Quicksort is an in-place sort that needs no temporary memory
  • Typically, quicksort is faster in practice than other algorithms, because its inner loop can be efficiently implemented on most architectures.
  • In most real-world data, it is possible to make design choices which minimize the probability of requiring quadratic time.
  • Quicksort tends to make excellent usage of the memory hierarchy like virtual memory or caches. It is well suited to modern computer architectures.
  • Quicksort can be easily parallelized due to its divide-and-conquer nature.

Disadvantages

  • This algorithm may swap the elements with equal comparison keys (it is not a stable sort).
  • Simpler algorithms like insertion sort perform better for the small (10 elements or about) data sets. The advanced implementations automatically switch into simpler alternative algorithm if the data set is small enough.
  • Quicksort does work very well on already mostly sorted lists or an lists with lots of similar values[2].

History

The quicksort algorithm was developed in 1960 by C. A. R. Hoare while in the Soviet Union, as a visiting student at Moscow University. At that time, Hoare worked in a project on machine translation and developed the algorithm in order to sort the words to be translated. This made them more easily matched to an already-sorted Russian-to-English dictionary that was stored on magnetic tape.[3]

Algorithm

Quicksort uses "divide and conquer strategy" to divide a list into two sub-lists.

The steps are:

  1. Pick an element, called a pivot, from the list (somewhere from the middle).
  2. Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
  3. Recursively sort the sub-list of lesser elements and the sub-list of greater elements.

The base case of the recursion are lists of size zero or one, which are always sorted.

The stage 2, reordering, can be implemented in various ways.

Naive partitioning

The simplest way is to create two initially empty lists, and then add all elements lower than pivot into the first list and elements greater then pivot to the second list. After that the two lists and pivot can be merged producing the required list. This approach uses additional memory for the transient lists and additional time to merge them, so may not be very efficient.

Dual loop with the meeting low and high values

The applet code demonstrates more efficient in-place partitioning:

  1. Set the two positions: low (initially start of the interval to reorder) and high (initially end of the interval).
  2. Move from low to high till finding value that is more than a pivot. This is the first candidate for swapping. Set low to the position of the found candidate.
  3. Move from high to low till finding value that is less than a pivot (do not cross the position of the first swapping candidate). This is the second candidate for swapping. Set high to the position of the second candidate.
  4. Swap both found candidates.
  5. Repeat while low < high, from the step 2. low and high need not to meet exactly at the pivot.

Single loop with storage index

This is the alternative algorithm, described in Wikipedia. It also works:

  1. Swap pivot with the last element in the section to partition (moving it out of the way).
  2. Set storage to the position of the first element.
  3. Move from start till end of the section. For every value that is less than a pivot, swap it with the value indexed by storage and then increment the storage.
  4. After finishing the previous step, swap the element indexed by storage with the pivot value that is at the end of the section. This moves the pivot in place.

Attempts to improve

Picking a value of the random element as the pivot value (step 1) makes the algorithm fast in the best possible case, but will still be very slow in the worst possible case. There are following known attempts to improve the pivot selections[4]:

  • Choose 3 numbers uniformly at random and keep the median of the 3 numbers as pivot.
  • Use some other algorithm to find the median of the data set and use this value as pivot.

Both suggestions improve the worst case performance but additional steps of picking pivot slow the algorithm for best case scenario. As a result, these extensions does not necessarily make the algorithm better for all possible cases.

Dual pivot

A "dual pivot" Quicksort has been proposed that in the source[5] is claimed to be faster in experimental measurements:

  1. Pick two pivots from the array rather than one.
  2. Reorder the array into three parts: all less than the smaller pivot, all larger than the larger pivot, all in between (or equal to) the two pivots.
  3. Recursively sort the sub-arrays.

Dual pivot quicksort will be used in Java Arrays.sort since the version 1.7. It is formally described in [6] that also contains the source code.

Parallelization

While individual in-place partition operations are difficult to parallelize, but once divided, different sections of the list can be sorted in parallel. If we have processors, we can divide a list of elements into sublists in average time, then sort each of these in average time. Ignoring the preprocessing, this is linear speedup. Given processors, only time is required overall.

One advantage of parallel quicksort over other parallel sort algorithms is that no synchronization is required. A new thread is started as soon as a sublist is available for it to work on and it does not communicate with other threads. When all threads complete, the sort is done.

References

  1. 1 Document, describing Quicksort algorithm at GateGuru
  2. 2 http://www.vogella.de/articles/JavaAlgorithms/article.html
  3. 3 An Interview with C.A.R. Hoare
  4. 4 Seminar topics at ETHZ
  5. 5 http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628
  6. 6 V.Yaroslavskiy (2009). Dual-Pivot Quicksort

See also

  • Freely available java code of this algorithm.
  • Proposal to replace Quicksort in OpenJDK by dual pivot sorting algorithm.

Acknowledgements

This web page reuses material from Wikipedia page http://en.wikipedia.org/wiki/Quicksort under the rights of CC-BY-SA license. As a result, the content of this page is and will stay available under the rights of this license regardless of restrictions that apply to other pages of this website.