Redigerer Kvikksortering (avsnitt)

==Historie==
[[Algoritme]]n quicksort ble utviklet av den [[Storbritannia|britiske]] [[informatikk|informatikeren]] [[Tony Hoare]] i 1959 mens han var utvekslingsstudent ved [[statsuniversitetet i Moskva]] i [[Sovjetunionen]].<ref name="CHM2017"/> På denne tiden arbeidet Hoare innenfor et prosjekt for [[maskinoversettelse]] som ble utført i regi av [[National Physical Laboratory]] i [[Teddington]], [[London]]. Under oversettelsen trengte han å sortere ord i [[russisk]]e setninger før han slo opp på ordene i en russisk-[[engelsk]] [[ordbok]] som allerede var sortert i alfabetisk rekkefølge på et [[magnetbånd]].<ref name="Shustek2009"/> Hans første idé var å benytte [[innstikksortering]], men etter å ha innsett at denne ville være treg, fikk han snart idéen om en ny [[sorteringsalgoritme]] som var quicksort. Han skrev et program i [[autokode]]n ''Mercury'' for partisjonen av ord, men klarte ikke å lage programmet slik at det tok hensyn til listen av usorterte segmenter. Da han kom tilbake til [[England]] ble han bedt om å skrive en kode for [[Shellsortering]] som del av hans nye jobb. Hoare nevnte for sin sjef at han visste om en raskere algoritme, men ble ikke trodd: Sjefen veddet en [[sixpence]] på at han ikke gjorde det, men ble til slutt nødt til å akseptere at han hadde tapt veddemålet. Senere lærte Hoare om [[programmeringsspråk]]et [[ALGOL (programmeringsspråk)|ALGOL]], og dets evne til å foreta [[rekursjon]]. Dette gjorde han i juli 1961 istand til å publisere koden i det [[vitenskapelig tidsskrift|vitenskapelige tidsskriftet]] ''[[Communications of the ACM]]'', som ble utgitt av [[Association for Computing Machinery]] i [[New York]].<ref name="Hoare1961"/><ref name="DeBarros2015"/>

Quicksort oppnådde raskt en stor utbredelse. I [[Forsknings-Unix|UNIX versjon 3]] (1973) ble algoritmen en del av sorteringsfunksjonen til standardbiblioteket i form av en rutine skrevet i [[assembler]].<ref name="Bell1972"/> I [[UNIX versjon 6]] (1975) ble en variant av quicksort skrevet av R. S. Scowen i standard [[C (programmeringsspråk)|K&R C]],<ref name="Bentley1993"/> og i 1983 ble algoritmen omskrevet for Unix-avarten [[Berkeley Software Distribution]].<ref name="Bentley1993"/> Algoritmen ble i 1973 implementert i [[C-standardbiblioteket]] i form av funksjonen {{mono|[[qsort]]}},<ref name="Wild2013"/> og i 1989 ble den standard i [[ANSI C]]/C90. Funksjonen er også en del av referanseimplementasjonen av [[Java (programmeringsspråk)|Java]].<ref name="Wild2013"/>

Den [[USA|amerikanske]] [[informatikk|informatikeren]] [[Robert Sedgewick]] ved [[Stanford University]], [[California]], publiserte i 1975 en [[doktoravhandling]] som blir betraktet som en milepæl innenfor studiet av quicksort.<ref name="Sedgewick1980"/> I denne avhandlingen løste han mange [[åpent problem|åpne problemer]] relatert til analyser av ulike måter å bruke «dreietapper» (''pivot'') på, deriblant [[samplesort]], adaptiv partisjonering av Maarten H. van Emden<ref name="Emden1970"/> så vel som derivasjoner av forventede antall sammenligninger og bytter.<ref name="Bentley1993"/> [[Jon Bentley]] fra [[Carnegie Mellon University]] i [[Pittsburgh]], [[Pennsylvania]], og [[Doug McIlroy|Malcolm McIlroy]] fra [[Massachusetts Institute of Technology]] inkorporerte i 1993 flere forbedringer for quicksort, til bruk for [[Bibliotek (programvare)|programvarebiblioteker]], deriblant en teknikk som håndterer like elementer og en «dreietapp»-metode som er kjent som ''pseudomedianen av ni'', hvor et utvalg av ni elementer deles opp i grupper på tre og [[median]]en av alle tre medianer i de tre gruppene blir valgt.<ref name="Bentley1993"/> Jon Bentley beskrev senere en annen enklere og mer kompakt metode i boken ''Programming Pearls'', som han tilegnet Nico Lumuto. Senere skrev Bentley at han hadde brukt Hoare’s versjon over mange år, men aldri hadde virkelig forstått den, og at Lomuto's versjon var enkel nok til å vise seg å være korrekt.<ref name="Oram2007"/> I det samme [[essay]] beskrev han quicksort som «den vakreste koden jeg noensinne har skrevet». Lomuto’s metode ble popularisert gjennom læreboken ''[[Introduction to Algorithms]]'' som utkom i 1990, selv om den er underlegen Hoare’s metode fordi den foretar tre ganger flere bytter i gjennomsnitt og har en kjøretid på {{math|''O''(''n''<sup>2</sup>)}} når alle elementene er identiske.<ref name="CS2017"/>

I 2009 foreslo den [[Russland|russiske]] informatikeren Vladimir Jaroslavskij en ny dobbel «dreietapp»-implementasjon av quicksort.<ref name="Jaroslavskij2009"/> I [[e-postliste]]n til Javakjernens [[runtimebibliotek]]  startet han en diskusjon hvor han hevdet at hans nye algoritme var overlegen bibliotekets sorteringsmetode, som på denne tiden var utbredt, og som benyttet en variant av den klassiske quicksort til Bentley og McIlroy.<ref name="HN1999"/> Hans versjon av quicksort ble i 2011 valgt som standard sorteringsalgoritme i versjon 7 av [[Oracle (selskap)|Oracle Corporation]]s runtimebibliotek for Java etter omfattende empiriske ytelsestester.<ref name="Wild2013"/>