Du algoritmai pseudokodu

Du algoritmai, viena idėja: skaidyk pusiau, spręsk dalis, sudėk atgal. Rekursija tau jau pažįstama iš 5 pamokos — ten ji buvo apėjimas, čia bus rikiavimas.

Skiriasi jie tuo, kur atliekamas darbas: suliejimo rikiavime — sudedant atgal, greitajame — skaidant.

Suliejimo rikiavimas

MergeSort(items):
    jei len(items) <= 1: grąžink kopiją
    mid ← len(items) / 2
    left  ← MergeSort(items[:mid])
    right ← MergeSort(items[mid:])
    grąžink Merge(left, right)

Merge(a, b):
    out ← tuščias, talpa len(a)+len(b)
    i ← 0; j ← 0
    kol i < len(a) ir j < len(b):
        cmp.Hit()
        jei a[i].Title <= b[j].Title:
            out ← out + a[i];  i ← i + 1
        kitaip:
            out ← out + b[j];  j ← j + 1
        moves.Hit()
    pridėk likusius iš a, tada iš b (kiekvienas moves.Hit())
    grąžink out

Skaidymas nieko nelygina. Visas darbas yra Merge, ir jis tiesinis: kiekvienas elementas paliečiamas vieną kartą. Gylių yra log₂ n, kiekviename gyliuje darbo n — iš to ir gaunasi O(n log n).

Vienas simbolis, kuriame gyvena stabilumas

jei a[i].Title <= b[j].Title

Tas <= reiškia: lygiavertėje situacijoje laimi KAIRĖ pusė. Kairė pusė yra ta, kuri masyve buvo anksčiau — taigi lygūs elementai išlaiko pradinę tvarką.

Parašyk < vietoj <=, ir rikiavimas vis tiek veiks. Testai, tikrinantys tik tvarką, praeis. Bet stabilumas dings — o kur tai svarbu, pamatysi 5 žingsnyje.

Greitasis rikiavimas

QuickSort(items):
    jei len(items) <= 1: grįžk
    p ← Partition(items, pivotIndex)
    QuickSort(items[:p])
    QuickSort(items[p+1:])

Partition(items, pivotIdx):
    perkelk items[pivotIdx] į priekį (moves.Hit(), jei judėjo)
    pivot ← items[0].Title
    i ← 1
    kiekvienam j nuo 1 iki len(items)-1:
        cmp.Hit()
        jei items[j].Title < pivot:
            sukeisk items[i] ir items[j];  moves.Hit();  i ← i + 1
    sukeisk items[0] ir items[i-1];  moves.Hit()
    grąžink i-1

Čia atvirkščiai: visas darbas yra skaidyme, o sudėti atgal nieko nereikia — kai abi pusės surikiuotos, masyvas jau surikiuotas.

Ir dirba jis vietoje: jokio antro masyvo, priešingai nei suliejimo rikiavimas.

Bet pivotas yra spėjimas

Partition padalija masyvą ties pivotu. Jei pivotas — mediana, gauni dvi lygias puses ir log₂ n gylį.

Jei pivotas — mažiausias elementas, kairė pusė tuščia, o dešinė turi n−1 elementą. Ir taip kiekviename žingsnyje.

Kada pivotas nuolat būna mažiausias? Kai imi pirmą elementą, o masyvas jau surikiuotas.

Spėk prieš skaitydamas toliau

Septintoje pamokoje -order sorted buvo įterpimo rikiavimo geriausias atvejis: 9 999 palyginimai vietoj 25 milijonų.

Ką ta pati vėliavėlė padarys greitajam rikiavimui su pirmo elemento pivotu?

Užsirašyk spėjimą. Dauguma mano, kad surikiuoti duomenys — lengvesnis darbas.