Kur elementarus rikiavimas laimi

Iki šiol viskas atrodė paprastai: O(n²) yra blogai, pusantros minutės yra ilgai, kitą pamoką sužinosi, kaip padaryti geriau.

Dabar pakeisk tvarką, o ne algoritmą.

Jau surikiuoti duomenys

$ algo sort -in s10k.jsonl -order sorted
n = 10000, order = sorted

algorithm         comparisons            swaps         wall
bubble                   9999                0           0s
selection            49995000                0    160.053ms
insertion                9999                0           0s

Įterpimo rikiavimas: 9 999 palyginimai vietoj 24 893 296. Du su puse tūkstančio kartų mažiau. Laikas — 0s, nes darbo tiek mažai, kad laikrodis nebemato (pirmoji pamoka, tas pats reiškinys).

Burbuliukų rikiavimas su swapped vėliavėle elgiasi lygiai taip pat.

O išrinkimo rikiavimas — 50 milijonų palyginimų, lygiai tiek pat, kiek ir išmėtytiems duomenims. Jis nepastebėjo, kad darbo nėra. Būtent tai reiškia „neturi geriausio atvejo".

Beveik surikiuoti — tikroji riba

Visiškai surikiuoti duomenys yra dirbtinis atvejis. Realiau: duomenys, kurie buvo surikiuoti, o paskui šiek tiek pakito. Sukeiskim 1 % pozicijų:

$ algo sort -in s10k.jsonl -order nearly
n = 10000, order = nearly

algorithm         comparisons            swaps         wall
bubble               49744722           632652    212.425ms
selection            49995000              100    157.292ms
insertion              642651           632652      1.491ms

1,5 milisekundės prieš 212 ir 157. Šimtą kartų greičiau už abu kitus, ir tas pats algoritmas, kuris prieš tai užtruko 92 ms.

Vienas procentas netvarkos — ir įterpimo rikiavimas vis dar praktiškai tiesinis.

Blogiausias atvejis

$ algo sort -in s10k.jsonl -order reverse
n = 10000, order = reverse

algorithm         comparisons            swaps         wall
bubble               49995000         49995000    379.949ms
selection            49995000             5000    167.647ms
insertion            49995000         49995000    180.245ms

Atvirkščiai surikiuoti duomenys — ir visi trys atlieka lygiai n(n−1)/2 palyginimų. Įterpimo rikiavimo pranašumas dingsta visiškai.

Vienas algoritmas, trys tvarkos, trys visiškai skirtingi rezultatai:

įterpimo rikiavimas	palyginimai	laikas
surikiuota (geriausias)	9 999	0 s
beveik surikiuota	642 651	1,5 ms
išmėtyta (vidutinis)	24 893 296	92 ms
atvirkščiai (blogiausias)	49 995 000	180 ms

Pirmoje pamokoje geriausias, vidutinis ir blogiausias atvejai buvo apibrėžimas. Dabar tai keturi skaičiai iš tavo programos, ir tarp kraštinių yra penki tūkstančiai kartų.

Tai kur čia nauda

Kyla natūralus klausimas: jei jau turi surikiuotus duomenis, kam juos rikiuoti?

Atsakymas — kad duomenys retai būna „surikiuoti" arba „ne". Jie būna beveik surikiuoti: pridėjai dešimt naujų įrašų prie milijono, atnaujinai kelis įvertinimus, sujungei du beveik tvarkingus sąrašus.

Įterpimo rikiavimas tokiais atvejais praktiškai tiesinis, o kiti du — ne.