Sortering i lineær tid og utvalg

En mur ingen sammenligningssortering kommer forbi

Merge-Sort, Quicksort og Heapsort har én ting til felles: de bestemmer rekkefølgen utelukkende ved å sammenligne par av elementer — er dette mindre enn hint? Vi kaller slike algoritmer sammenligningssortering. Det viser seg at uansett hvor smart en slik algoritme er, kan den aldri komme under $\Theta (n\lg n)$ i verste fall. Det er ikke et spørsmål om å være flink nok; det er en matematisk mur.

For å bevise muren modellerer vi en hvilken som helst sammenligningssortering som et beslutningstre. Hver indre node er én sammenligning, og de to grenene ut av noden er de to mulige svarene (mindre eller ikke). Hvert løv svarer til én ferdig sortert rekkefølge — én permutasjon av inndataene.

Nå kommer poenget. For at sorteringen skal fungere på alle mulige inndata, må hver av de $n!$ permutasjonene kunne ende i sitt eget løv. Treet må altså ha minst $n!$ løv. Et binærtre med høyde $h$ har høyst $2^h$ løv, så vi trenger $2^h\ge n!$. Antall sammenligninger i verste tilfelle er nettopp høyden $h$:

ƒhøyde av beslutningstreet

Tar vi logaritmen og bruker at $\lg (n!)=\Theta (n\lg n)$ (Stirlings formel), får vi den nedre grensen:

ƒnedre grense for sammenligningssortering

Konklusjonen er presis og litt overraskende: ingen algoritme som kun sammenligner elementer kan i verste fall slå $\Theta (n\lg n)$. Merge-Sort og Heapsort er altså ikke bare gode — de er asymptotisk optimale i denne klassen.

Snik forbi muren med ekstra antakelser

Muren gjelder kun algoritmer som ikke vet noe om elementene utover hvordan de ordnes innbyrdes. Men hva om vi vet mer? Hva om nøklene er heltall i et lite, kjent område? Da kan vi sortere uten å sammenligne i det hele tatt, og slippe under $\Theta (n\lg n)$. Det er ingen motsigelse — vi bryter ikke muren, vi går rundt den ved å bruke informasjon sammenligningssorteringene ikke har.

Den første slike algoritmen er counting-sort. Anta nøklene er heltall i området $0$ til $k$. Da teller vi ganske enkelt hvor mange ganger hver verdi forekommer, og bruker tellingene til å plassere hvert element direkte på rett sted.

COUNTING-SORT(A, k):
    C = [0, 0, ..., 0]            # k+1 tellere, alle 0
    for x in A:                   # tellefasen: O(n)
        C[x] = C[x] + 1
    for i in 1..k:                # akkumuler: prefikssummer, O(k)
        C[i] = C[i] + C[i-1]
    B = [tom, ..., tom]           # resultatarray, lengde n
    for x in reversed(A):         # plasser bakfra for stabilitet
        C[x] = C[x] - 1
        B[C[x]] = x
    return B

Etter tellefasen gjør vi tellerne om til prefikssummer: $C[i]$ skal fortelle hvor mange elementer som er mindre enn eller lik $i$. Da vet vi nøyaktig hvilken sluttposisjon hvert element skal ha. For eksempelet over blir den akkumulerte $C$ lik $[2,2,4,7,7,8]$ — det siste elementet med nøkkel 3 skal altså på indeks 6, det nest siste på indeks 5, og så videre. Vi plasserer hvert element direkte uten en eneste sammenligning mellom to nøkler.

Kjøretiden er summen av to gjennomløp, ett over de $n$ elementene og ett over de $k$ tellerne:

ƒcounting-sort

Når $k=O(n)$ er dette lineært. Prisen er $\Theta (k)$ ekstra minne til tellerne, så Counting-Sort egner seg når tallområdet er lite i forhold til antall elementer. Skal du sortere en million heltall mellom 0 og 100, er den uslåelig. Skal du sortere en million 64-bits tall, er $k$ astronomisk, og Counting-Sort kollapser — du ville trengt et tellerarray med flere celler enn det finnes atomer i nærheten. Dette spennet mellom triumf og kollaps er hele poenget: lineær-tid-sorteringene kjøper farten sin ved å anta noe konkret om nøklene, og bryter sammen så snart antakelsen ryker.

Stabilitet — den egenskapen som gjør Radix mulig

Legg merke til siste løkke i Counting-Sort: vi går gjennom inndataene bakfra. Det er ikke tilfeldig. Det gjør sorteringen stabil sortering — to elementer med lik nøkkel beholder sin innbyrdes rekkefølge fra inndataene. Stabilitet høres ut som en detalj, men den er selve forutsetningen for neste algoritme.

radix-sort sorterer flersifrede nøkler ett siffer om gangen, fra det minst signifikante til det mest signifikante. For tallene 329, 457, 657, 839, 436, 720, 355 sorterer vi først på enerne, så på tierne, så på hundrerne. Det kontraintuitive er at vi starter med det minst viktige sifferet. Det fungerer kun fordi hver enkelt siffersortering er stabil: når vi sorterer på tierne, bevarer stabiliteten den rekkefølgen enerne allerede ga, så tall med samme tier kommer riktig sortert på eneren.

ƒradix-sort

Her er $d$ antall sifre og $k$ basen (for desimaltall $k=10$). Hver av de $d$ rundene er en Counting-Sort på ett siffer. Med fast antall sifre er Radix-Sort lineær i $n$ — nok en gang ved å utnytte at nøklene har struktur sammenligningssorteringer ikke ser.

Prøv selv å se hvorfor rekkefølgen er viktig. Hadde vi sortert mest signifikante siffer først, ville en senere sortering på et mindre viktig siffer stokket om på den grovgrupperingen vi nettopp laget, og resultatet ble galt. Ved å gå fra minst til mest signifikant, og holde hvert steg stabilt, lar vi de viktigere sifrene få siste ord mens de mindre viktige bevares som tie-breaker. Det er et lite, vakkert eksempel på hvordan en tilsynelatende teknisk egenskap — stabilitet — gjør hele algoritmen mulig.

Bucket-Sort: når dataene er jevnt fordelt

En tredje vei rundt muren bygger på en antakelse om fordelingen av nøklene. bucket-sort forutsetter at nøklene er jevnt fordelt over et intervall, for eksempel reelle tall mellom 0 og 1. Vi deler intervallet i $n$ like store bøtter, slår hvert element i bøtta det hører hjemme i, sorterer hver bøtte for seg, og leser bøttene i rekkefølge.

Poenget er statistisk. Når nøklene er jevnt fordelt, havner det i snitt konstant mange elementer i hver bøtte, og å sortere en bøtte med konstant størrelse koster konstant tid. Summert over alle bøttene blir det lineært i forventning:

ƒbucket-sort, forventet

Merk ordet «forventet». Bucket-Sort gir ingen garanti i verste fall — er dataene klumpet sammen i én bøtte, degenererer den til den lokale sorteringens kjøretid. Den er rask når antakelsen om jevn fordeling holder, og det er en helt annen kontrakt enn Merge-Sorts ubetingede $\Theta (n\lg n)$.

Utvalg: finn det k-te minste uten å sortere

Til slutt et beslektet problem. utvalgsproblemet spør etter det $k$-te minste elementet i en samling — medianen er spesialtilfellet $k=n/2$. Den enkle løsningen er å sortere alt og slå opp på indeks $k$, men det koster $\Theta (n\lg n)$, og vi gjør mye unødig arbeid: vi ordner hele samlingen bare for å lese ut ett element.

randomized-select gjenbruker partisjoneringen fra Quicksort, men med et avgjørende kutt. Den partisjonerer rundt et tilfeldig pivot, akkurat som Quicksort, men deretter graver den kun videre i den ene siden som inneholder det $k$-te elementet. Den andre siden kastes helt — vi vet svaret ikke kan ligge der.

RANDOMIZED-SELECT(A, lo, hi, k):
    if hi - lo == 1:
        return A[lo]
    p = RANDOMIZED-PARTITION(A, lo, hi)
    rank = p - lo                       # pivotens posisjon i delarrayet
    if k == rank:
        return A[p]                     # pivoten ER svaret
    elif k < rank:
        return RANDOMIZED-SELECT(A, lo, p, k)        # bare venstre
    else:
        return RANDOMIZED-SELECT(A, p + 1, hi, k - rank - 1)  # bare høyre

Fordi vi forkaster én side, blir det forventede arbeidet en geometrisk avtagende rekke i stedet for $\lg n$ fulle nivåer. Partisjoneringen kaster i snitt bort en konstant brøk av elementene per steg, og summen $n+n/2+n/4+\dots$ konvergerer til $\Theta (n)$:

ƒrandomisert utvalg, forventet

Vi finner altså medianen i forventet lineær tid — raskere enn å sortere. Akkurat som med Quicksort er det det tilfeldige pivotvalget som gjør forventningen god; verste fall er fortsatt $\Theta (n^2)$, men praktisk talt umulig å fremtvinge.