Sorteerimisalgoritmide võidusõit

Mullsortimine teeb halvimal juhul täpselt n(n−1)/2 võrdlust — umbes 2000 juhul n=64. Iga läbimine peab läbi käima kogu allesjäänud sortimata piirkonna ilma varem väljumata. Kiirsortimise partitsioneerimine paneb pöördelemendi selle lõplikku kohta ja jagab probleemi kaheks alamprobleemiks; iga rekursioonitase teeb O(n) tööd O(log n) taseme jooksul, andes kokku O(n log n). Konks: kui pöördelement satub alati ühte otsa — näiteks sorditud sisend viimase elemendiga pöördena — halveneb partitsioneerimine n suurusega n−1, n−2, ... alamprobleemideks, mis annavad kokku O(n²). Siin kasutatud keskmise elemendi pöördeelement väldib seda, mistõttu vastupidine sisend jääb kiireks. Väheste unikaalsete väärtustega on huvitav juhtum: kui paljud elemendid võrduvad pöördega, raiskab identsete väärtuste vahetamine tööd ja võib lähendada ruutkeerukusele. Big-O ütleb sulle kasvuklassi; konstandid, sisendi tundlikkus ja vahemälu käitumine otsustavad, millist algoritmi sa tegelikult kasutad.

See võistlus hindab iga algoritmi võrdluste ja vahetuste arvu järgi, mitte stopperiga. Tegelik kulunud aeg sõltub sinu protsessorist, brauserist ja muudest töötavatest programmidest, nii et sama kood võib eri masinatel tunduda kiire või aeglane. Operatsioonide loendamine annab puhta ja korratava mõõdu tehtud tööst: sama sisend annab alati samad arvud, nii et võrdled algoritme endid, mitte riistvara.

Tony Hoare leiutas Quicksorti 1959. aastal Moskvas külalisüliõpilasena, töötades masintõlke projekti kallal. Vene lause sõnaraamatust otsimiseks pidi ta selle sõnad esmalt tähestikku seadma — ja tavapärane meetod oli lootusetult aeglane. Tema lahendus, pivot-elemendi ümber jagamine, sai üheks enim kasutatud algoritmiks üldse. Siin võistlevad tulbad pärinevad keeleprobleemist, mitte arvutusülesandest.