Content deleted Content added
m added math mode along with clarifying the stack space should be log_2 instead of log2 |
Undid revision 1227313414 by Bieco blu (talk): not the singer, the author of A UNIX primer |
||
Line 27:
Quicksort gained widespread adoption, appearing, for example, in [[Unix]] as the default library sort subroutine. Hence, it lent its name to the [[C standard library]] subroutine {{mono|[[qsort]]}}<ref name="engineering" /> and in the reference implementation of [[Java (programming language)|Java]].
[[Robert Sedgewick (computer scientist)|Robert Sedgewick]]'s PhD thesis in 1975 is considered a milestone in the study of Quicksort where he resolved many open problems related to the analysis of various pivot selection schemes including [[Samplesort]], adaptive partitioning by Van Emden<ref>{{Cite journal |title=Algorithms 402: Increasing the Efficiency of Quicksort |journal=Commun. ACM |date=1970-11-01 |issn=0001-0782 |pages=693–694 |volume=13 |issue=11 |doi=10.1145/362790.362803 |first=M. H. |last=Van Emden| s2cid=4774719|doi-access=free }}</ref> as well as derivation of expected number of comparisons and swaps.<ref name="engineering" /> [[Jon Bentley (computer scientist)|Jon Bentley]] and [[Douglas McIlroy|Doug McIlroy]] in 1993 incorporated various improvements for use in programming libraries, including a technique to deal with equal elements and a pivot scheme known as ''pseudomedian of nine,'' where a sample of nine elements is divided into groups of three and then the median of the three medians from three groups is chosen.<ref name="engineering" /> Bentley described another simpler and compact partitioning scheme in his book ''Programming Pearls'' that he attributed to [[Nico Lomuto]]
== Algorithm ==
| |||