Others view: Matrix ♦ Welcome ♦ Reversal potential ♦ 2-3-4 tree ♦ Dissociated press ♦ Dot-Bracket Notation ♦ rss.xml ♦ A star algorithm ♦ Moebius transformation ♦

Redirected from Quicksort

- Quicksort is an in-place sort that needs no temporary memory
- Typically, quicksort is faster in practice than other [[Math:c|\mathcal{O}(n \ log \ n)]] 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.

- 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]}.

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]}

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

The steps are:

- Pick an element, called a
*pivot*, from the list (somewhere from the middle). - 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. - 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.

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.

The applet code demonstrates more efficient in-place partitioning:

- Set the two positions:
*low*(initially start of the interval to reorder) and*high*(initially end of the interval). - 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. - 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. - Swap both found candidates.
- Repeat while
*low*<*high*, from the step 2.*low*and*high*need not to meet exactly at the pivot.

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

- Swap pivot with the last element in the section to partition (moving it out of the way).
- Set
*storage*to the position of the first element. - 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*. - 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.

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.

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

- Pick two pivots from the array rather than one.
- 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.
- 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.

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 [[Math:c|p]] processors, we can divide a list of [[Math:c|n]] elements into [[Math:c|p]] sublists in [[Math:c|\mathcal{O}(n)]] average time, then sort each of these in [[Math:c|\textstyle\mathcal{O}\left(\frac{n}{p} \log\frac{n}{p}\right)]] average time. Ignoring the [[Math:c|\mathcal{O}(n)]] preprocessing, this is linear speedup. Given [[Math:c|n]] processors, only [[Math:c|\mathcal{O}(n)]] 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.

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

- 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.