Pivotas: kur kvadratas grįžta

Palygink su spėjimu iš antro žingsnio.

Išmėtyti duomenys — viskas gerai

$ algo dc -in s10k.jsonl -order shuffled
n = 10000, order = shuffled

algorithm                   comparisons            moves         wall
merge                            120440           133616        7.5ms
quick (first pivot)              149913            75946      2.005ms
quick (median-of-3)              146520            78217      2.999ms
quick (random)                   156381            89939      2.499ms

Visi keturi ~120–156 tūkstančiai palyginimų. Septintoje pamokoje tas pats masyvas įterpimo rikiavimui kainavo 24 893 296. Skirtumas — 200 kartų, ir tai visos šios pamokos priežastis.

Greitasis rikiavimas atlieka daugiau palyginimų nei suliejimo, bet yra greitesnis: dirba vietoje, tad juda mažiau duomenų (75 946 prieš 133 616).

Surikiuoti duomenys — ir štai kur

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

algorithm                   comparisons            moves         wall
merge                             64608           133616      6.583ms
quick (first pivot)            49995000             9999    325.219ms
quick (median-of-3)              131343            70826          1ms
quick (random)                   159057            89759      2.008ms

49 995 000. Iš 149 913.

Tai 333 kartus daugiau palyginimų ir 162 kartus ilgiau — vien todėl, kad duomenys jau buvo tvarkingi.

Ir tas skaičius pažįstamas: 49 995 000 = n(n−1)/2. Tiksliai tiek pat, kiek septintos pamokos burbuliukų ir išrinkimo rikiavimai. Greitasis rikiavimas su pirmo elemento pivotu surikiuotiems duomenims yra elementarus rikiavimas.

Ta pati -sorted vėliavėlė, kuri septintoje pamokoje davė įterpimo rikiavimui geriausią atvejį, čia duoda blogiausią. Tai antrasis iš trijų atsipirkimų, pažadėtų pirmoje pamokoje.

Suliejimo rikiavimui tuo tarpu net lengviau: 64 608 vietoj 120 440. Jis neturi blogo atvejo — testas tai tikrina visoms trims tvarkoms.

Pivoto taisymas — ir kur jis nepakanka

Mediana iš trijų surikiuotus duomenis išgelbsti visiškai: 131 343 vietoj 49 995 000. 380 kartų geriau, ir net kiek mažiau nei išmėtytiems.

Bet paleisk atvirkščiai surikiuotus:

$ algo dc -in s10k.jsonl -order reverse
algorithm                   comparisons            moves         wall
merge                             69008           133616      5.004ms
quick (first pivot)            49995000         25009999    506.951ms
quick (median-of-3)             8379139          4187234     94.662ms
quick (random)                   151569            87173      2.083ms

Mediana iš trijų: 8 379 139. Ne 50 milijonų, bet ir ne 146 tūkstančiai — 57 kartus daugiau nei išmėtytiems duomenims.

Ar tai vis dar kvadratinis augimas? Pamatuok su dviem n:

n	mediana iš trijų, atvirkščiai	santykis
1 000	86 890	—
10 000	8 379 139	×96

Dešimteriopas n — šimteriopas darbas. Taip, vis dar kvadratinis, tik su maždaug šešis kartus mažesne konstanta.

Atsitiktinis pivotas tuo pačiu metu: 10 837 → 151 569, tai ×14 — būtent tokio augimo ir tikimasi iš O(n log n).

Mediana iš trijų sutvarko tą atvejį, kurį tikrini. Atsitiktinis pivotas sutvarko ir tuos, kurių netikrinai.