Sorteerimisalgoritmide võidusõit

jälgi samm-sammult, kuidas kaks algoritmi võistlevad samal sisendil — võrdlused, vahetused, keerukus

Interaktiivse simulatsiooni laadimine...

Big-O pole kogu lugu 🖖

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.

Miks loeb samme, mitte sekundeid 🖖

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.

Quicksort sündis vene keelt tõlkides 🖖

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.

Ülesanne täielikult lahendatud

Mullisortimise vahetuste arvu täpne ennustamine 64 ümberpööratud elemendi korral 7 sammu
Käivita võidusõit eelseadistusega pööratud — 64 elementi, suurim esimesena. Ennusta mullsordi vahetuste arvu täpselt, mitte selle kasvujärku; seejärel ütle, mis takistab ühelgi naaberelemente vahetaval algoritmil seda ületamast.
1. Inversioon on paar, mis asub vales suhtelises järjestuses. Pööratud sisend on äärmuslik juhtum: iga i < j korral on varasem element suurem, seega on iga paar inversioonis ja nende arv ongi kõigi paaride kogusumma. Arvuta see arv enne, kui miski liigub — osutub, et see ongi kogu ülesande võti.
  
  $I = # {(i, j) : i < j, a_{i} > a_{j}} = (2 64) = \frac{64 \times 63}{2} = 2, 016$
2. Mullsort vahetab ainult naabreid ja seda vaid siis, kui need on vales järjestuses. Selline vahetus parandab selle ühe paari ega häiri ühtegi teist, sest kaks liikuvat elementi säilitavad sama suhte kõige muuga väljaspool neid. Üks vahetus, üks inversioon — mitte kunagi kaks, mitte kunagi null.
  
  $a_{k} > a_{k + 1} ⟶ I \mapsto I - 1$
3. Sorditud olek tähendab nulli inversiooni. Alustades 2 016-st ja eemaldades vahetuse kohta täpselt ühe, ei jää manööverdamisruumi: vahetuste arv on paratamatu. Paneel kuvab 2 016 vahetust ja see on pigem samasus kui halvima juhu tõke.
  
  $S = I_{0} - 0 = 2, 016$
4. Võrdlused on eraldi loendur, mis siin juhtumisi kokku langeb. Läbimine i vaatleb vahemikku j = 0 … 62 − i, seega kogusumma on 63 + 62 + ⋯ + 1 — sama 2 016, mida näitab rida mullsordi halvim juhtum n(n−1)/2. Võrdsed arvud tähendavad, et iga viimane kui võrdlus leidis inversiooni, mis ongi see, mida "halvim juhtum" siin tähendab. Loendur iga paneeli pealkirja all loendab ühe sammu võrdluse ja ühe sammu vahetuse kohta, seega kuvab see enne alustamist samm 0 / 4 032 ning nupp › kulutab ühe klõpsuga täpselt ühe neist sammudest. Pealkirja kõrval olev O(n²) on silt, mitte loendur.
  
  $C = i = 0 \sum 62 (63 - i) = 63 + 62 + \dots + 1 = \frac{63 \times 64}{2} = 2, 016 = \frac{n ( n - 1 )}{2}, C + S = 4, 032$
5. Üldista nüüd 2. sammu, sest just seda kiirsortimine ära kasutab. Kahe elemendi vahetamine, mis asuvad d positsiooni võrra üksteisest eemal, jätab iga paari, mis moodustatakse vahemikust väljaspool asuva elemendiga, kokkuvõttes puutumata: sellist elementi võrreldakse uuesti teise otsaga, kaks võrdlust vahetavad kohad ja selle panus jääb muutmata. Muutuda saab paar ise, pluss need 2(d − 1) paari, mida kumbki ots moodustab vahele jääva d − 1 elemendiga. Iga vahetusega saab eemaldada maksimaalselt 2d − 1 inversiooni ja seades d = 1, saame tagasi 2. sammu ühe inversiooni.
  
  $1 + 2 (d - 1) = 2 d - 1 (d = 1 \Rightarrow 1)$
6. Kiirsortimise esimene partisioon võtab keskmise elemendi tugielemendiks, a[31] = 33, ning vahetab (0, 63), (1, 62), … , (31, 32) — 32 vahetust kaugustel 63, 61, … , 1. 5. samm piirab nende kogumõju 2 016 inversiooniga ning see ainus läbimine jätab massiivi täielikult sordituks, seega eemaldati täpselt 2 016. Ülempiir saavutatakse võrdsusena: igaüks 32 vahetusest saavutas oma maksimumi.
  
  $p = a_{31} = 33, d = 63, 61, \dots, 1 : m = 1 \sum 32 (2 (2 m - 1) - 1) = m = 1 \sum 32 (4 m - 3) = 2, 112 - 96 = 2, 016$
7. Seega ei võistle need kaks algoritmi nutikuses, vaid ulatuses. Kiirsortimise kuvatud 334 võrdlust ja 64 vahetust annavad summaks 398 selle loenduril — ning vaid 32 neist vahetustest liigutavad midagi, ülejäänud 32 on tugielemendi vahetamised iseendaga lõikudes, mis on juba järjestatud. Selle 334 jääb samuti alla kuvatud võrdlusalusele n·log₂n väärtusega 384, sest pööratud jada keskmine element on selle mediaan, mistõttu iga tükeldus on võrdne.
  
  $334 + 64 = 398, 64 lo g_{2} 64 = 384, \frac{2 , 016}{32} = 63$
Vastus

2 016 vahetust ja 2 016 võrdlust — loenduri 4 032 sammu. Ning 2 016 ei ole fakt mullsordi kohta: see on alumine piir tervele perekonnale. Iga algoritm, millel on lubatud vahetada vaid naaberelemente — pistesortimine, kokteilisortimine, gnoomisortimine või mõni, mida keegi pole veel kirjutanud —, eemaldab 2. sammu kohaselt vahetuse kohta maksimaalselt ühe inversiooni, mistõttu vajavad need kõik sellel sisendil vähemalt 2 016 vahetust ning need kõik on pööratud andmete korral Ω(n²)-keerukusega seetõttu, millises mudelis need töötavad, mitte seepärast, et need oleksid kömakad. Kiirsortimine pääseb sellest alumisest piirist, sest tal on lubatud liigutada elementi 63 kohta korraga: 32 tegeliku vahetusega eemaldatud 2 016 inversiooni teeb 63 inversiooni vahetuse kohta, ning 5. samm ütleb, et see on maksimaalne, mida ükski vahetus üle selle kauguse oleks suutnud saavutada. Paneel ei arvuta inversioonide arvu ega sellest tulenevat alumist piiri.

$S \geq I_{0} = (2 64) = 2, 016 (d = 1), \frac{I _{0}}{32} = 63$

Õpitee

Loe tööd, mitte sekundeid

Viib edasi recursion-tree

Allikad (1)

Insight block 3 — quicksort as its author published it: C. A. R. Hoare, "Quicksort." The Computer Journal 5(1), 10–16, 1962. The algorithm first appeared the year before as C. A. R. Hoare, "Algorithm 64: Quicksort", Communications of the ACM 4(7), 321, 1961.

42Mathi meeskond · Uuendatud 2026-05-27

Kontrollitud avaldatud allikate põhjal. Parandused on teretulnud. Toimetamispõhimõtted · Parandused

Kõik Arvutustehnika õppetunnid →

Näiteülesanded

peaaegu sorditud - Sisendi jaotus muudab algoritmide suhtelist tõhusust.
vastupidine - Mullsortimine teeb 2 016 võrdlust ja 2 016 vahetust. Iga võrdlus leiab eest vale järjestuse, sest 64 elemendi ümberpööramine pöörab korraga ringi kõik 2 016 paari. Kiirsortimine saab hakkama 334 võrdluse ja 64 vahetusega, jäädes alla oma n·log₂n baasväärtusele 384. Tagurpidi massiivi keskmine element on nimelt igal jaotussammul täpselt mediaan.
vähe unikaalseid väärtusi - Kaheksakümmend elementi, mis pärinevad vaid kaheksast erinevast väärtusest. Kiirsortimisel kulub 534 võrdlust oma n·log₂n baasväärtuse 506 vastu. See on kolmest seadistusest ainuke, kus algoritm tõuseb oma joonest kõrgemale: juhtelemendiga võrdsed elemendid vahetatakse ringi, kuid sellest pole mingit kasu. Mullsortimine teeb ikka oma kindlad 3 160 võrdlust, aga vahetusi koguneb ainult 1 330. Nii paljud naaberpaarid on juba niigi õiges järjekorras.