FACTOID # 11: Oklahoma has the highest rate of women in State or Federal correctional facilities.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
RELATED ARTICLES
People who viewed "Quicksort" also viewed:
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Quicksort
Quicksort in action on a list of numbers. The horizontal lines are pivot values.
Quicksort in action on a list of numbers. The horizontal lines are pivot values.

Quicksort is a well-known sorting algorithm developed by C. A. R. Hoare that, on average, makes mathcal{O}(n~log~n) (big O notation) comparisons to sort n items. However, in the worst case, it makes mathcal{O}(n^2) comparisons. Typically, quicksort is significantly faster in practice than other mathcal{O}(n~log~n) 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 possibility of requiring quadratic time. Q Methodology is a research method used in psychology and other social sciences to study peoples subjectivity -- that is, their viewpoint. ... Image File history File links Sorting_quicksort_anim. ... In computer science and mathematics, a sorting algorithm is an algorithm that puts elements of a list in a certain order. ... Sir Charles Antony Richard Hoare (Tony Hoare or C.A.R. Hoare, born January 11, 1934) is a British computer scientist, probably best known for the development of Quicksort, the worlds most widely used sorting algorithm, in 1960. ... In computer science, best and worst cases in a given algorithm express what the resource usage is at least and at most, respectively. ... For other uses, see Big O. In computational complexity theory, big O notation is often used to describe how the size of the input data affects an algorithms usage of computational resources (usually running time or memory). ... In computer science, best and worst cases in a given algorithm express what the resource usage is at least and at most, respectively. ...


Quicksort is a comparison sort and, in efficient implementations, is not a stable sort. A comparison sort is a particular type of sorting algorithm; a number of well-known algorithms are comparison sorts. ... In computer science and mathematics, a sorting algorithm is an algorithm that puts elements of a list in a certain order. ...

Contents

History

The quicksort algorithm was developed by Hoare in 1960 while working for the small British scientific computer manufacturer Elliott Brothers.[1] Elliott Brothers (London) Ltd was an early computer company of the 1950s–60s in the United Kingdom. ...


Algorithm

Quicksort sorts by employing a divide and conquer strategy to divide a list into two sub-lists. In computer science, divide and conquer (D&C) is an important algorithm design paradigm. ... Look up list in Wiktionary, the free dictionary. ...


The steps are:

  1. Pick an element, called a pivot, from the list.
  2. 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.
  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 algorithm always terminates because it puts at least one element in its final place on each iteration (the loop invariant). The pivot or pivot element is the element of a matrix, which is selected first by an algorithm (e. ... A common method of simplification is to divide a problem into subproblems of the same type. ... Recursion in computer programming defines a function in terms of itself. ...


In simple pseudocode, the algorithm might be expressed as: Pseudocode (derived from pseudo and code) is a compact and informal high-level description of a computer programming algorithm that uses the structural conventions of programming languages, but omits detailed subroutines, variable declarations or language-specific syntax. ...

 function quicksort(array) var list lessOrEqual, greater if length(array) ≤ 1 return array select a pivot value pivot from array for each x in array if x ≤ pivot then add x to lessOrEqual if x > pivot then add x to greater return concatenate(quicksort(lessOrEqual), quicksort(greater)) 

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. A comparison sort is a particular type of sorting algorithm; a number of well-known algorithms are comparison sorts. ...


Version with in-place partition

In-place partition in action on a small list. The boxed element is the pivot element, blue elements are less or equal, and red elements are larger.
In-place partition in action on a small list. The boxed element is the pivot element, blue elements are less or equal, and red elements are larger.

The disadvantage of the simple version above is that it requires Ω(n) extra storage space, which is as bad as mergesort (see big-O notation for the meaning of Ω). The additional memory allocations required can also drastically impact speed and cache performance in practical implementations. There is a more complicated version which uses an in-place partition algorithm and can achieve mathcal{O}(log~n) space use on average for good pivot choices: Image File history File links Partition_example. ... Image File history File links Partition_example. ... In computer science, merge sort or mergesort is a sort algorithm for rearranging lists (or any other data structure that can only be accessed sequentially, e. ... The Big O notation is a mathematical notation used to describe the asymptotic behavior of functions. ... In computer science, algorithms work-in-place if they transform a data structure using a minimal, constant amount of extra memory (or disk) space. ...

 function partition(array, left, right, pivotIndex) pivotValue := array[pivotIndex] swap array[pivotIndex] and array[right] // Move pivot to end storeIndex := pivoteIndex // it can't be left initially. // gotta be pivotIndex. for i  from  left to right // left ≤ i < right if array[i] ≤ pivotValue swap array[i] and array[storeIndex] storeIndex := storeIndex + 1 swap array[storeIndex] and array[right] // Move pivot to its final place return storeIndex 

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:

 function quicksort(array, left, right) if right > left select a pivot index (e.g. pivotIndex := left) pivotNewIndex := partition(array, left, right, pivotIndex) quicksort(array, left, pivotNewIndex-1) quicksort(array, pivotNewIndex+1, right) 

However, since partition reorders elements within a partition, this version of quicksort is not a stable sort.


Parallelizations

Like 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 p processors, we can divide a list of n elements into p sublists in mathcal{O}(n) average time, then sort each of these in mathcal{O}left(frac{n}{p}~logfrac{n}{p}right) average time. Ignoring the mathcal{O}(n) preprocessing, this is linear speedup. Given n processors, only mathcal{O}(n) time is required overall. In computer science, merge sort or mergesort is a sort algorithm for rearranging lists (or any other data structure that can only be accessed sequentially, e. ... In computer science, a parallel algorithm, as opposed to a traditional serial algorithm, is one which can be executed a piece at a time in many different processing devices, and then put back together again at the end to get the correct result. ... In parallel computing, speedup refers to how much a parallel algorithm is faster than a corresponding sequential algorithm. ...


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[2]. For example, in 1991 David Powers described a parallelized quicksort that can operate in mathcal{O}(log~n) time given enough processors by performing partitioning implicitly[3].


Formal analysis

From the initial description it's not obvious that quicksort takes mathcal{O}(n~log~n) time on average. It's not hard to see that the partition operation, which simply loops over the elements of the array once, uses mathcal{O}(n) time. In versions that perform concatenation, this operation is also mathcal{O}(n).


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 log~n nested calls before we reach a list of size 1. This means that the depth of the call tree is mathcal{O}(log~n). 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 mathcal{O}(n) time all together (each call has some constant overhead, but since there are only mathcal{O}(n) calls at each level, this is subsumed in the mathcal{O}(n) factor). The result is that the algorithm uses only mathcal{O}(n~log~n) time. In computer science, a call stack is a special stack which stores information about the active subroutines of a computer program. ...


An alternate approach is to set up a recurrence relation for the T(n) factor, the time needed to sort a list of size n. Because a single quicksort call involves mathcal{O}(n) factor work plus two recursive calls on lists of size frac{n}{2} in the best case, the relation would be: In mathematics, a recurrence relation, also known as a difference equation, is an equation which defines a sequence recursively: each term of the sequence is defined as a function of the preceding terms. ...

mathrm{T}(n) = mathcal{O}(n) + 2mathrm{T}(frac{n}{2}).

The master theorem tells us that mathrm{T}(n) = mathcal{O}(n~log~n). In the analysis of algorithms, the master theorem, which is a specific case of the Akra-Bazzi theorem, provides a cookbook solution in asymptotic terms for recurrence relations of types that occur in practice. ...


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 100~log~n, so the total running time is still mathcal{O}(n~log~n).


In the worst case, however, the two sublists have size 1 and n − 1, and the call tree becomes a linear chain of n nested calls. The ith call does mathcal{O}(n-i) work, and sum_{i=0}^n (n-i) = mathcal{O}(n^2). The recurrence relation is:

mathrm{T}(n) = mathcal{O}(n)~+~mathrm{T}(1)~+~mathrm{T}(n-1) = mathcal{O}(n)~+~mathrm{T}(n-1)

This is the same relation as for insertion sort and selection sort, and it solves to mathrm{T}(n) = mathcal{O}(n^2). Example of insertion sort sorting a list of random numbers. ... Selection sort is a sorting algorithm, specifically an in-place comparison sort. ...


Randomized quicksort expected complexity

Randomized quicksort has the desirable property that it requires only mathcal{O}(n~log~n) expected time, regardless of the input. But what makes random pivots a good choice? In probability theory the expected value (or mathematical expectation) of a random variable is the sum of the probability of each possible outcome of the experiment multiplied by its payoff (value). Thus, it represents the average amount one expects as the outcome of the random trial when identical odds are...


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 2~log_2~n times before reaching lists of size 1, yielding an mathcal{O}(n~log~n) algorithm.


Unfortunately, a random choice will only choose from these middle parts half the time. The surprising fact is that this is good enough. Imagine that you are flipping a coin over and over until you get k heads. Although this could take a long time, on average only 2~k flips are required, and the chance that you won't get k heads after 100~k flips is infinitesimally small. By the same argument, quicksort's recursion will terminate on average at a call depth of only 2~(2~log_2~n). But if its average call depth is mathcal{O}(log~n), and each level of the call tree processes at most n elements, the total amount of work done on average is the product, mathcal{O}(n~log~n).


Average complexity

Even if pivots aren't chosen randomly, quicksort still requires only mathcal{O}(n~log~n) 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 n 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:

mathrm{C}(n) = n - 1 + frac{1}{n} sum_{i=0}^{n-1} (mathrm{C}(i)+mathrm{C}(n-i-1)) = 2n ln n = 1.39n log_2 n.

Here, n − 1 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.

 C(n) = (n-1) + C(n/2) + C(n/2) = (n-1) + 2C(n/2) = (n-1) + 2((n/2) - 1 + 2C(n/4)) = n + n + 4C(n/4) - 1 - 2 = n + n + n + 8C(n/8) - 1 - 2 - 4 = ... = kn + 2^kC(n/(2^k)) - (1 + 2 + 4 + . . . . . + 2^(k-1)) where log2n > k > 0 = kn + 2^kC(n/(2^k)) - 2^k + 1 -> nlog2n + nC(1) - n + 1. 

Space complexity

The space used by quicksort depends on the version used.


Quicksort has a space complexity of mathcal{O}(log~n), even in the worst case, when it is carefully implemented such that

  • in-place partitioning is used. This requires mathcal{O}(1).
  • After partitioning, the partition with the fewest elements is (recursively) sorted first, requiring at most mathcal{O}(log~n) space. Then the other partition is sorted using tail-recursion or iteration. (This idea is commonly attributed to R.M.Sedgewick [1][2][3])

The version of quicksort with in-place partitioning uses only constant additional space before making any recursive call. However, if it has made mathcal{O}(log~n) nested recursive calls, it needs to store a constant amount of information from each of them. Since the best case makes at most mathcal{O}(log~n) nested recursive calls, it uses mathcal{O}(log~n) space. The worst case makes mathcal{O}(n) nested recursive calls, and so needs mathcal{O}(n) 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 mathcal{O}(log~n) bits to index into a list of n items. Because we have variables like this in every stack frame, in reality quicksort requires mathcal{O}(log^2n) bits of space in the best and average case and mathcal{O}(n~log~n) 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 mathcal{O}(n~log~n) bits of space.


The not-in-place version of quicksort uses mathcal{O}(n) space before it even makes any recursive calls. In the best case its space is still limited to mathcal{O}(n), because each level of the recursion uses half as much space as the last, and

sum_{i=0}^{infty} frac{n}{2^i} = 2n.

Its worst case is dismal, requiring

sum_{i=0}^n (n-i+1) = mathcal{O}(n^2)

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 mathcal{O}(log~n) bits, leading to a best-case mathcal{O}(n~log~n) and worst-case mathcal{O}(n^2~log~n) space requirement.


Selection-based pivoting

A selection algorithm chooses the kth 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 mathcal{O}(n) time, and makes it an in-place algorithm. A variation on this algorithm brings the worst-case time down to mathcal{O}(n) (see selection algorithm for more information). In computer science, a selection algorithm is an algorithm for finding the kth smallest number in a list, called order statistics. ... In computer science, an in-place algorithm is an algorithm which transforms a data structure using a small, constant amount of extra storage space. ... In computer science, a selection algorithm is an algorithm for finding the kth smallest number in a list, called order statistics. ...


Conversely, once we know a worst-case mathcal{O}(n) 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 mathcal{O}(n~log~n) running time. In practical implementations, however, this variant is considerably slower on average.


Competitive 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. In computer science, a binary search tree (BST) is a binary tree where every node has a value, every nodes left subtree has values less than or equal to the nodes value, and every right subtree has values greater. ...


The most direct competitor of quicksort is heapsort. Heapsort is typically somewhat slower than quicksort, but the worst-case running time is always O(n log n). Quicksort is usually faster, though there remains the chance of worst case performance except in the introsort variant. 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 Θ(log n) space. However, heapsort requires efficient random access to be practical. A run of the heapsort algorithm sorting an array of randomly permuted values. ... For other uses, see Big O. In computational complexity theory, big O notation is often used to describe how the size of the input data affects an algorithms usage of computational resources (usually running time or memory). ... Introsort or introspective sort is a sorting algorithm designed by David Musser in 1997. ...


Quicksort also competes with mergesort, another recursive sort algorithm but with the benefit of worst-case O(n log n) 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 storage or 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 Ω(n) auxiliary space in the best case, whereas the variant of quicksort with in-place partitioning and tail recursion uses only O(log n) space. (Note that when operating on linked lists, mergesort only requires a small, constant amount of auxiliary storage.) In computer science, merge sort or mergesort is a sort algorithm for rearranging lists (or any other data structure that can only be accessed sequentially, e. ... In computer science and mathematics, a sorting algorithm is an algorithm that puts elements of a list in a certain order. ... In computer science, a linked list is one of the fundamental data structures, and can be used to implement other data structures. ... Disk storage is a category of data storage mechanisms for computers; data is recorded on planar surfaces or disks for temporary or permanent storage. ... Network-attached storage (NAS) systems are generally computing-storage devices that can be accessed over a computer network, rather than directly being connected to the computer (via a computer bus). ...


Notes

  1. ^ Timeline of Computer History: 1960. Computer History Museum.
  2. ^ R.Miller, L.Boxer, Algorithms Sequential & Parallel, A Unified Approach, Prentice Hall, NJ, 2006
  3. ^ David M. W. Powers, Parallelized Quicksort with Optimal Speedup, Proceedings of International Conference on Parallel Computing Technologies. Novosibirsk. 1991.

Location of Novosibirsk in Russia and the Oblast Coordinates: Oblast Novosibirsk  - Mayor Vladimir Gorodetskiy Area    - City 447. ...

References

  • 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. ACM 4(7), 321-322, 1961
  • 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 Press and 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. Analysis of Quicksort. CS 332: Designing Algorithms. Department of Computer Science, University of Wales Swansea.
  • Steven Skiena. 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, "Engineering a Sort Function, SOFTWARE---PRACTICE AND EXPERIENCE, VOL. 23(11), 1249--1265, 1993

Communications of the ACM (CACM) is the flagship monthly magazine of the Association for Computing Machinery (ACM). ... Donald Ervin Knuth ( or Ka-NOOTH[1], Chinese: [2]) (b. ... Thomas H. Cormen is the co-author of Introduction to Algorithms, along with Charles Leiserson, Ron Rivest, and Cliff Stein. ... Charles E. Leiserson is a computer scientist, specializing in the theory of parallel computing and distributed computing, and particularly practical applications thereof; as part of this effort, he developed the Cilk multithreaded language. ... Professor Ron Rivest Professor Ronald Linn Rivest (born 1947, Schenectady, New York) is a cryptographer, and is the Viterbi Professor of Computer Science at MITs Department of Electrical Engineering and Computer Science. ... Clifford Stein is a computer scientist, currently working as a professor at Columbia University in New York, NY. He earned his BSE from Princeton University in 1987, a MS from Massachusetts Institute of Technology in 1989, and a PhD from Massachusetts Institute of Technology in 1992. ... Cover of the second edition Introduction to Algorithms is a book by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. ... MIT Press Books The MIT Press is a university publisher affiliated with the Massachusetts Institute of Technology (MIT) in Cambridge, Massachusetts. ... The McGraw-Hill Companies, Inc. ... Faron George Moller (born 1962) is a Canadian-born British computer scientist. ... The State University of New York at Stony Brook (SUNYSB), also known as Stony Brook University (SBU) is a public research university located in Stony Brook, New York (on the north side of Long Island, about 55 miles east of Manhattan, New York). ...

See also

Introsort or introspective sort is a sorting algorithm designed by David Musser in 1997. ... Flashsort is a sorting algorithm with extremely good efficiency for balanced data sets published in 1998 by Karl-Dietrich Neubert. ...

External links

Wikibooks
Wikibooks Algorithm implementation has a page on the topic of
Quicksort

  Results from FactBites:
 
PlanetMath: quicksort (231 words)
Quicksort is a divide-and-conquer algorithm for sorting in the comparison model.
The behavior of quicksort can be analyzed by considering the computation as a binary tree.
This is version 10 of quicksort, born on 2003-10-07, modified 2006-08-06.
Quicksort (789 words)
Quicksort is a sorting algorithm which, on average, needs Θ(n log(n)) comparisons to sort n items.
Quicksort is usually faster, but needs lots of extra care to avoid the worst-case behaviour problems.
quicksort :: Ord a => [a] -> [a] quicksort [] = [] quicksort (h:t) = (quicksort [y
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m