Du algoritmai pseudokodu

Skaičiavimo rikiavimas

Trys perėjimai, jokių palyginimų.

CountingSortByRating(items):
    k ← MaxRating - MinRating + 1
    count ← masyvas iš k nulių

    // 1. Suskaičiuok, kiek kartų pasitaiko kiekvienas įvertinimas.
    kiekvienam it iš items:
        count[it.Rating - MinRating] += 1

    // 2. Prefiksinės sumos: count[v] tampa indeksu VIENU DAUGIAU nei
    //    paskutinė v vieta rezultate.
    kiekvienam i nuo 1 iki k-1:
        count[i] += count[i-1]

    // 3. Išdėliok. ATGAL — ir būtent tai daro rikiavimą stabilų.
    out ← masyvas, len(items) dydžio
    kiekvienam i nuo len(items)-1 žemyn iki 0:
        v ← items[i].Rating - MinRating
        count[v] -= 1
        out[count[v]] ← items[i]
        moves.Hit()
    grąžink out

Perskaityk trečią perėjimą dar kartą. Nėra nė vieno palyginimo tarp dviejų įrašų. Raktas nurodo vietą tiesiogiai.

Sudėtingumas — O(n + k): n perėjimams per duomenis, k prefiksinėms sumoms.

Kodėl atgal

Prefiksinė suma duoda vietą paskutiniam tos reikšmės elementui. Einant nuo galo, paskutinis įrašas atsiduria paskutinėje savo bloko vietoje, priešpaskutinis — priešpaskutinėje, ir pradinė tvarka išlieka.

Eik pirmyn — ir lygūs elementai išeis atvirkščiai. Vienas ciklo krypties pakeitimas, ir stabilumo nebėra. Šeštame žingsnyje pamatysi, kad tai ne smulkmena.

Skaitmeninis rikiavimas

Skaičiavimo rikiavimui reikia k dydžio masyvo. Metams tai 131 — priimtina. O jei raktas būtų visas int64?

Skaitmeninis rikiavimas (radix) tą problemą apeina: rikiuoja po vieną skaitmenį, ir kiekvienam skaitmeniui k yra tik 10.

RadixSortByYear(items):
    out ← items kopija
    kiekvienam d nuo 0 iki 3:          // vienetai, dešimtys, šimtai, tūkstančiai
        out ← countingPass(out, d)     // stabilus skaičiavimo rikiavimas
    grąžink out

Nuo mažiausiai reikšmingo skaitmens. Keturi perėjimai vietoj vieno, bet kiekvienas su dešimčia kibirų vietoj 131.

Ir čia įsijungia stabilumas

Kai rikiuoji pagal dešimtis, vienetų tvarka jau sutvarkyta. Antrasis perėjimas privalo ją išsaugoti — kitaip pirmojo darbas dingsta.

Būtent tai daro stabilus rikiavimas.

Septintoje pamokoje stabilumas buvo savybė. Aštuntoje — pasekmė. Čia jis yra teisingumo sąlyga: be jo skaitmeninis rikiavimas ne netvarkingas, o klaidingas.

Šeštame žingsnyje tai pamatysi kaip du skaičius ir vieną false.