Quicksort in action on a list of numbers. The horizontal lines are pivot values.
time= on average
space=Varies by implementation
Stability= [Sorting_algorithm#Classification|Not Stable]
Quicksort is a well-known
sorting algorithmdeveloped by C. A. R. Hoarethat, on average, makes ( big O notation) comparisons to sort "n" items. However, in the worst case, it makes comparisons. Typically, quicksort is significantly faster in practice than other algorithms, because its inner loop can be efficiently implemented on most architectures, and in most real-world data it is possible to make design choices which minimize the probability of requiring quadratic time.
Quicksort is a
comparison sortand, in efficient implementations, is not a stable sort.
The quicksort algorithm was developed by
C. A. R. Hoarein 1962 while working for the small British scientific computer manufacturer Elliott Brothers. [cite web |url=http://www.computerhistory.org/timeline/?year=1960 |title=Timeline of Computer History: 1960 |publisher=Computer History Museum]
The steps are:
# Pick an element, called a "pivot", from the list.
# Reorder the list so that all elements which are less than the pivot come before the pivot and so that all elements 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.
pseudocode, the algorithm might be expressed as this:
Notice that we only examine elements by comparing them to other elements. This makes quicksort a
comparison sort. This version is also a stable sort (considering that the "for each" method retrieves elements in original order, and the pivot selected is the last among those of equal value).
The correctness of the partition algorithm is based on the following two arguments:
*At each iteration, all the elements processed so far are in the desired position: before the pivot if less than or equal to the pivot's value, after the pivot otherwise (loop invariant).
*Each iteration leaves one fewer element to be processed (loop variant).
The correctness of the overall algorithm follows from inductive reasoning: for zero or one element, the algorithm leaves the data unchanged; for a larger data set it produces the concatenation of two parts, elements less than or equal to the pivot and elements greater than it, themselves sorted by the recursive hypothesis.
The disadvantage of the simple version above is that it requires extra storage space, which is as bad as
mergesort. The additional memory allocations required can also drastically impact speed and cache performance in practical implementations. There is a more complex version which uses an in-placepartition algorithm and can achieve the complete sort using space use on average (for the call stack):
This is the in-place partition algorithm. It partitions the portion of the array between indexes "left" and "right", inclusively, by moving all elements less than or equal to
a [pivotIndex]to the beginning of the subarray, leaving all the greater elements following them. In the process it also finds the final position for the pivot element, which it returns. It temporarily moves the pivot element to the end of the subarray, so that it doesn't get in the way. Because it only uses exchanges, the final list has the same elements as the original list. Notice that an element may be exchanged multiple times before reaching its final place.
This form of the partition algorithm is not the original form; multiple variations can be found in various textbooks, such as versions not having the storeIndex. However, this form is probably the easiest to understand.
Once we have this, writing quicksort itself is easy:
However, since "partition" reorders elements within a partition, this version of quicksort is not a stable sort.
mergesort, quicksort can also be easily parallelized due to its divide-and-conquer nature. 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.
Other more sophisticated parallel sorting algorithms can achieve even better time bounds [R.Miller, L.Boxer, Algorithms Sequential & Parallel, A Unified Approach, Prentice Hall, NJ, 2006] . For example, in 1991 David Powers described a parallelized quicksort that can operate in time given enough processors by performing partitioning implicitly [David M. W. Powers, [http://citeseer.ist.psu.edu/327487.html Parallelized Quicksort with Optimal Speedup] , "Proceedings of International Conference on Parallel Computing Technologies".
Novosibirsk. 1991.] .
From the initial description it's not obvious that quicksort takes time on average. It's not hard to see that the partition operation, which simply loops over the elements of the array once, uses time. In versions that perform concatenation, this operation is also .
In the best case, each time we perform a partition we divide the list into two nearly equal pieces. This means each recursive call processes a list of half the size. Consequently, we can make only nested calls before we reach a list of size 1. This means that the depth of the call tree is . But no two calls at the same level of the call tree process the same part of the original list; thus, each level of calls needs only time all together (each call has some constant overhead, but since there are only calls at each level, this is subsumed in the factor). The result is that the algorithm uses only time.
An alternate approach is to set up a
recurrence relationfor the factor, the time needed to sort a list of size . Because a single quicksort call involves factor work plus two recursive calls on lists of size in the best case, the relation would be:
master theoremtells us that .
In fact, it's not necessary to divide the list this precisely; even if each pivot splits the elements with 99% on one side and 1% on the other (or any other fixed fraction), the call depth is still limited to , so the total running time is still .
In the worst case, however, the two sublists have size 1 and (for example, if the array consists of the same element by value), and the call tree becomes a linear chain of nested calls. The th call does work, and . The recurrence relation is:
This is the same relation as for
insertion sortand selection sort, and it solves to .Given knowledge of which comparisons are performed by the sort, there are adaptive algorithms that are effective at generating worst-case input for quicksort on-the-fly, regardless of the pivot selection strategy. [M. D. McIlroy. A Killer Adversary for Quicksort. Software Practice and Experience: vol.29, no.4, 341–344. 1999. [http://citeseer.ist.psu.edu/212772.html At Citeseer] ]
Randomized quicksort expected complexity
Randomized quicksort has the desirable property that it requires only expected time, regardless of the input. But what makes random pivots a good choice?
Suppose we sort the list and then divide it into four parts. The two parts in the middle will contain the best pivots; each of them is larger than at least 25% of the elements and smaller than at least 25% of the elements. If we could consistently choose an element from these two middle parts, we would only have to split the list at most times before reaching lists of size 1, yielding an algorithm.
A random choice will only choose from these middle parts half the time. However, this is good enough. Imagine that you are flipping a coin over and over until you get heads. Although this could take a long time, on average only flips are required, and the chance that you won't get heads after flips is highly improbable. By the same argument, quicksort's recursion will terminate on average at a call depth of only . But if its average call depth is , and each level of the call tree processes at most elements, the total amount of work done on average is the product, . Note that the algorithm does not have to verify that the pivot is in the middle half - if we hit it any constant fraction of the times, that's enough for the desired complexity.
The outline of a formal proof of the expected time complexity follows. Assume that there are no duplicates as duplicates could be handled with linear time pre- and post-processing, or considered cases easier than the analyzed. Choosing a pivot, uniformly at random from to , is then equivalent to choosing the size of one particular partition, uniformly at random from to . With this observation, the continuation of the proof is analogous to the one given in the average complexity section.
Even if pivots aren't chosen randomly, quicksort still requires only time over all possible permutations of its input. Because this average is simply the sum of the times over all permutations of the input divided by factorial, it's equivalent to choosing a random permutation of the input. When we do this, the pivot choices are essentially random, leading to an algorithm with the same running time as randomized quicksort.
More precisely, the average number of comparisons over all permutations of the input sequence can be estimated accurately by solving the recurrence relation:
Here, is the number of comparisons the partition uses. Since the pivot is equally likely to fall anywhere in the sorted list order, the sum is averaging over all possible splits.
This means that, on average, quicksort performs only about 39% worse than the ideal number of comparisons, which is its best case. In this sense it is closer to the best case than the worst case. This fast average runtime is another reason for quicksort's practical dominance over other sorting algorithms.
The space used by quicksort depends on the version used.
Quicksort has a space complexity of , even in the worst case, when it is carefully implemented such that
* in-place partitioning is used. This requires .
* After partitioning, the partition with the fewest elements is (recursively) sorted first, requiring at most space. Then the other partition is sorted using tail-recursion or iteration. (This idea is commonly attributed to R.Sedgewick [http://www.cs.columbia.edu/~hgs/teaching/isp/hw/qsort.c ] [http://www.ugrad.cs.ubc.ca/~cs260/chnotes/ch6/Ch6CovCompiled.html ] [http://home.tiscalinet.ch/t_wolf/tw/ada95/sorting/index.html ] )
The version of quicksort with in-place partitioning uses only constant additional space before making any recursive call. However, if it has made nested recursive calls, it needs to store a constant amount of information from each of them. Since the best case makes at most nested recursive calls, it uses space. The worst case makes nested recursive calls, and so needs space.
We are eliding a small detail here, however. If we consider sorting arbitrarily large lists, we have to keep in mind that our variables like "left" and "right" can no longer be considered to occupy constant space; it takes bits to index into a list of items. Because we have variables like this in every stack frame, in reality quicksort requires bits of space in the best and average case and space in the worst case. This isn't too terrible, though, since if the list contains mostly distinct elements, the list itself will also occupy bits of space.
The not-in-place version of quicksort uses space before it even makes any recursive calls. In the best case its space is still limited to , because each level of the recursion uses half as much space as the last, and
Its worst case is dismal, requiring
space, far more than the list itself. If the list elements are not themselves constant size, the problem grows even larger; for example, if most of the list elements are distinct, each would require about bits, leading to a best-case and worst-case space requirement.
selection algorithmchooses the "k"th smallest of a list of numbers; this is an easier problem in general than sorting. One simple but effective selection algorithm works nearly in the same manner as quicksort, except that instead of making recursive calls on both sublists, it only makes a single tail-recursive call on the sublist which contains the desired element. This small change lowers the average complexity to linear or time, and makes it an in-place algorithm. A variation on this algorithm brings the worst-case time down to (see selection algorithmfor more information).
Conversely, once we know a worst-case 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 running time. In practical implementations, however, this variant is considerably slower on average.
Another variant is to choose the Median of Medians as the pivot element instead of the median itself for partitioning the elements. While maintaining the asymptotically optimal run time complexity of (by preventing worst case partitions), it is also considerably faster than the variant that chooses the median as pivot.
The C implementation of the above algorithm:
Comparison with other sorting algorithms
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.
The most direct competitor of quicksort is
heapsort. Heapsort is typically somewhat slower than quicksort, but the worst-case running time is always . Quicksort is usually faster, though there remains the chance of worst case performance except in the introsortvariant. 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 space. However, heapsort requires efficient random access to be practical.
Quicksort also competes with
mergesort, another recursive sort algorithm but with the benefit of worst-case running time. Mergesort is a stable sort, unlike quicksort and heapsort, and can be easily adapted to operate on linked lists and very large lists stored on slow-to-access media such as disk storageor network attached storage. Although quicksort can be written to operate on linked lists, it will often suffer from poor pivot choices without random access. The main disadvantage of mergesort is that, when operating on arrays, it requires auxiliary space in the best case, whereas the variant of quicksort with in-place partitioning and tail recursion uses only space. (Note that when operating on linked lists, mergesort only requires a small, constant amount of auxiliary storage.) Bucket sortwith two buckets is very similar to quicksort; the pivot in this case is effectively the value in the middle of the value range, which does well on average for uniformly distributed inputs.
*Brian C. Dean, "A Simple Expected Running Time Analysis for Randomized 'Divide and Conquer' Algorithms." "Discrete Applied Mathematics" 154(1): 1-5. 2006.
*Hoare, C. A. R. "Partition: Algorithm 63," "Quicksort: Algorithm 64," and "Find: Algorithm 65."
Comm. ACM4(7), 321-322, 1961
*Hoare, C. A. R. [http://dx.doi.org/10.1093/comjnl/5.1.10 "Quicksort."] Computer Journal 5 (1): 10-15. (1962). (Reprinted in Hoare and Jones: [http://portal.acm.org/citation.cfm?id=SERIES11430.63445 "Essays in computing science"] , 1989.)
*R. Sedgewick. Implementing quicksort programs, Comm. ACM, 21(10):847-857, 1978.
*David Musser. Introspective Sorting and Selection Algorithms, Software Practice and Experience vol 27, number 8, pages 983-993, 1997
Donald Knuth. "The Art of Computer Programming", Volume 3: "Sorting and Searching", Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Pages 113–122 of section 5.2.2: Sorting by Exchanging.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. " Introduction to Algorithms", Second Edition. MIT Pressand McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 7: Quicksort, pp.145–164.
*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.
Faron Moller. [http://www.cs.swan.ac.uk/~csfm/Courses/CS_332/quicksort.pdf Analysis of Quicksort] . CS 332: Designing Algorithms. Department of Computer Science, University of Wales Swansea.
* Steven Skiena. [http://www.cs.sunysb.edu/~algorith/lectures-good/node5.html Lecture 5 - quicksort] . CSE 373/548 - Analysis of Algorithms. Department of Computer Science.
State University of New York at Stony Brook.
* Conrado Martínez and Salvador Roura, "Optimal sampling strategies in quicksort and quickselect." SIAM J. Computing 31(3):683-705, 2001.
* Jon L. Bentley and M. Douglas McIlroy, [http://citeseer.ist.psu.edu/bentley93engineering.html Engineering a Sort Function] , "Software—Practice and Experience", Vol. 23(11), 1249–1265, 1993
* [http://www.atkinson.yorku.ca/~sychen/research/sorting/sortingHome.html Quicksort applet] with "level-order" recursive calls to help improve algorithm analysis
* [http://www.wanginator.de/studium/applets/quicksort_en.html Quicksort Java Applet]
* [http://fiehnlab.ucdavis.edu/staff/wohlgemuth/java/quicksort Multidimensional quicksort in Java]
* [http://en.literateprograms.org/Category:Quicksort Literate implementations of Quicksort in various languages] on LiteratePrograms
* [http://www.mycsresource.net/articles/programming/sorting_algos/quicksort/ Quicksort tutorial with illustrated examples]
* [http://vision.bc.edu/~dmartin/teaching/sorting/anim-html/quick.html A graphical demonstration and discussion of 2-way partition quick sort]
* [http://vision.bc.edu/~dmartin/teaching/sorting/anim-html/quick3.html A graphical demonstration and discussion of 3-way partition quick sort]
* [http://coderaptors.com/?QuickSort A colored graphical Java applet] which allows experimentation with initial state and shows statistics
Wikimedia Foundation. 2010.
Look at other dictionaries:
Quicksort — en acción sobre una lista de números aleatorios. Las líneas horizontales son valores pivote. El ordenamiento rápido (quicksort en inglés) es un algoritmo creado por el científico británico en computación C. A. R. Hoare basado en la técnica de… … Wikipedia Español
Quicksort — [dt. »Schnellsortierung«], ein Algorithmus zum Sortieren von Daten, der 1962 von dem britischen Informatiker Sir Antony (C. A. R., Tony) Hoarse (*Colombo, Sri Lanka 1934) erfunden wurde. Die Grundidee besteht darin, einen zu sortierenden… … Universal-Lexikon
Quicksort — Eine zufällige Permutation von Integerwerten wird mit Quicksort sortiert. Die blauen Linien zeigen den Wert des rot markierten Pivotelements im jeweiligen Rekursionsschritt. Quicksort (von englisch quick ‚schnell‘ und to sort ‚sortieren‘)… … Deutsch Wikipedia
Quicksort — Tri rapide Le tri rapide (en anglais quicksort) est une méthode de tri inventée par C.A.R. Hoare en 1961 et fondée sur la méthode de conception diviser pour régner. Il peut être implémenté sur un tableau (tri sur place) ou sur des listes ;… … Wikipédia en Français
quicksort — 1. noun A sorting algorithm that operates by recursively partitioning the items to be sorted into two sets. Somewhat surprisingly, the average behaviour of quicksort is the same as the best behaviour. 2. verb To sort with such an algorithm … Wiktionary
Quicksort — El ordenamiento rápido (quicksort en inglés) es un algoritmo basado en la técnica de divide y conquista, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n. Esta es probablemente la técnica de ordenamiento más… … Enciclopedia Universal
Quicksort — … Википедия
quicksort — ● ►en /kouik sort/ n. m. ►ALGO Tri par Segmentation . Algorithme classique de tri, considéré comme l un des plus rapides, qui effectue un nombre de comparaison de l ordre de nlog(n) pour le tri de n éléments … Dictionnaire d'informatique francophone
Quicksort — Quick|sort [ kwiksɔ:t] <zu engl. to sort »sortieren«> ein schnelles, rechnerinternes Sortierverfahren (EDV) … Das große Fremdwörterbuch
Algoritmo de ordenamiento — Quicksort en acción sobre una lista de números aleatorios. Las líneas horizontales son valores pivote. En computación y matemáticas un algoritmo de ordenamiento es un algoritmo que pone elementos de una lista o un vector en una secuencia dada por … Wikipedia Español