Jis jau yra standartinėje bibliotekoje

Praeitas žingsnis baigėsi klausimu: kodėl įterpimo rikiavimas beveik surikiuotiems duomenims laimi prieš sort.Slice iki maždaug 2 000, o paskui pralaimi?

Atsakymo nerasi savo kode. Jis yra Go standartinės bibliotekos kode.

sort.Slice viduje

sort.Slice iškviečia pdqsort — greitojo rikiavimo atmainą, kurią sutiksi kitą pamoką. Bet jos pirmasis sprendimas toks:

// src/sort/zsortfunc.go
const maxInsertion = 12

for {
    length := b - a
    if length <= maxInsertion {
        insertionSort_func(data, a, b)
        return
    }
    ...
}

Kai atkarpa sumažėja iki dvylikos elementų ar mažiau, pdqsort nustoja skaidyti ir iškviečia įterpimo rikiavimą.

Ne kaip atsarginį variantą. Kaip įprastą, dažniausiai vykdomą kelią: skaidydamas masyvą per pusę, algoritmas didžiąją dalį laiko dirba su mažomis atkarpomis.

sort.SliceStable — dar tiesmukiškiau

// src/sort/zsortfunc.go
func stable_func(data lessSwap, n int) {
    blockSize := 20
    a, b := 0, blockSize
    for b <= n {
        insertionSort_func(data, a, b)
        a = b
        b += blockSize
    }
    ...
}

Stabilus standartinės bibliotekos rikiavimas pradeda nuo to, kad įterpimo rikiavimu sutvarko kiekvieną 20 elementų bloką, ir tik paskui juos sulieja.

Ir dar viena vieta — partialInsertionSort_func, kviečiama su komentaru „The slice is likely already sorted". Tai tas pats greitkelis, kurį ką tik pamatavai savo kode.

Tai kodėl sort.Slice laimi prie n = 10 000

Ne todėl, kad ji nenaudoja įterpimo rikiavimo. Todėl, kad ji naudoja jį tik ten, kur jis geras — mažoms atkarpoms — o dideliam masyvui pirmiau pritaiko skaidymą, kurio tu dar nemoki.

Ji nėra alternatyva įterpimo rikiavimui. Ji yra įterpimo rikiavimas plius kai kas daugiau, ir tas „kas daugiau" yra kita pamoka.

Išvada, kurią verta įsidėmėti

Elementarūs rikiavimai nėra pralaimėjusios praeities technologijos. Jie yra komponentai. Jie pralaimi kaip savarankiškas sprendimas dideliems duomenims ir laimi ten, kur duomenų mažai arba jie beveik tvarkingi — o būtent tokie atvejai sudaro didžiąją dalį darbo bet kuriame rimtame rikiavime.

Burbuliukų rikiavimas šioje istorijoje nedalyvauja. Jis nėra niekur viduje, ir jo vienintelė vieta yra ši pamoka: jis rodo, kaip atrodo O(n²) tada, kai niekas jo nesušvelnina.