Stabilumas kaip teisingumo sąlyga

Skaitmeninis rikiavimas remiasi tuo, kad kiekvienas perėjimas išsaugo ankstesnių darbą. Patikrinkim, kas nutinka, kai neišsaugo.

$ algo radix -in s100k.jsonl
n = 100000, key = Year (1900..2030), 4 passes of base-10 counting sort

inner pass                        comparisons          moves         wall sorted?
stable (backwards)                          0         400000     22.256ms true
UNSTABLE (forwards)                         0         400000      16.21ms false

first break in the unstable run, at index 737:
  1909 1909 1909 1908 1908 1908

Perskaityk lentelę atidžiai.

Palyginimų: 0 ir 0. Vienodai. Judesių: 400 000 ir 400 000. Vienodai. Laikas: panašus. sorted?: true ir false.

Tas pats algoritmas, tas pats darbo kiekis, tie patys duomenys. Vienas ciklo krypties simbolis — ir vienas rezultatas teisingas, o kitas ne.

Kaip lūžis atrodo

1909 1909 1909 1908 1908 1908

Metai mažėja. Rikiuojant tūkstančių skaitmenį, visi šie įrašai turi tą patį 1, tad perėjimas jų neturėjo perstatinėti — tik išsaugoti tvarką, kurią sudėliojo šimtų, dešimčių ir vienetų perėjimai.

Nestabilus perėjimas tą tvarką apvertė. 1908 ir 1909, sutvarkyti anksčiau, susikeitė vietomis, nes jų tūkstančių skaitmuo lygus.

Trečias ir stipriausias stabilumo teiginys

pamoka	ką reiškė stabilumas
7	savybė. Išrinkimo rikiavimas jos neturi — trūkumas, bet rikiuoja teisingai
8	pasekmė. Daugiaraktė tvarka sugriūva; transit du grafai nesutaria
9	teisingumo sąlyga. Be jos algoritmas grąžina neteisingą atsakymą

Septintoje pamokoje nestabilus rikiavimas vis tiek surikiuodavo. Aštuntoje jis surikiuodavo pagal prašytą raktą ir sugriaudavo ankstesnį. Čia jis nesurikiuoja apskritai.

Skaitmeninis rikiavimas nėra „geresnis su stabiliu vidiniu perėjimu". Jis yra stabilus vidinis perėjimas, pakartotas keturis kartus. Atimk stabilumą ir nebeliks algoritmo.

Kodėl testas tikrina abu

ncsort_test.go reikalauja, kad RadixSortByYearUnstable nesurikiuotų, ir kad abu variantai atliktų tiek pat darbo. Ta pati forma kaip septintoje ir aštuntoje pamokose: trūkumas tvirtinamas, kad liktų matomas.

Jei kada nors „pataisysi" countingPassUnstable, testas praneš — ir demonstracija bus prarasta, o ne kodas pagerintas.