Rangering i lineær tid

Merge-Sort bruker $\Theta(n \lg n)$ tid, og ingen algoritme som bare sammenligner elementer parvis, kan gjøre det bedre i verste tilfelle. Grensen gjelder så lenge algoritmen bare sammenligner, og svaret skal være hele den sorterte tabellen. Ber du om mindre enn en sortert tabell, for eksempel bare det $i$-ende minste elementet, eller antar du mer om inputen, for eksempel at verdiene er små heltall, går det i lineær tid.

Sorteringsgrensen

Insertion-Sort, Merge-Sort og Quicksort får bare vite noe om elementene gjennom tester som $a_i \le a_j$. De er sammenligningsbaserte. Hver test har to utfall, så alt en slik algoritme kan gjøre på $n$ elementer, kan tegnes som et binært tre. Hver indre node er en sammenligning, hver løvnode er en ferdig rekkefølge, og én kjøring er stien fra rota til en løvnode.

Tre elementer kan stå i $3! = 6$ rekkefølger, og hver av dem må være en løvnode. Et binært tre med høyde 2 har plass til bare fire løvnoder, så minst én input krever tre sammenligninger.

Generelt må treet ha en løvnode for hver av de $n!$ permutasjonene av inputen, for hver av dem er riktig svar for en eller annen input. Et binært tre med høyde $h$ har høyst $2^h$ løvnoder, så $2^h \ge n!$ og $h \ge \lg n!$. Høyden er antall sammenligninger langs den lengste stien, altså i verste tilfelle. Stirlings formel gir $n! > (n/e)^n$, og dermed

Grensen er en nedre grense for verste tilfelle. Den sier at den dyreste instansen krever minst $\lg n!$ sammenligninger, og $\lg n! = \Omega(n \lg n)$. Mer sier den ikke. En algoritme kan gjerne være verre, og i beste tilfelle kan den være bedre: Insertion-Sort bruker $\Theta(n)$ på sortert input. Beste tilfelle er $\Omega(n)$ uansett, for hvert element må leses. Gjennomsnittet er $\Omega(n \lg n)$ som det verste, for en tilfeldig permutasjon krever i snitt $\lg n!$ ja/nei-svar å skille fra de andre.

1 Init(A, n)
2 Main(A, n)

Randomized-Select

Det $i$-ende minste elementet i en tabell har rang $i$. Rang 1 er minimum, rang $n$ maksimum, og medianen har rang $\lfloor (n+1)/2 \rfloor$, den nederste av de to midterste når $n$ er partall. Sortering og oppslag finner elementet i $\Theta(n \lg n)$, men du ber om mindre enn en sortert tabell, så sorteringsgrensen gjelder ikke. Verdiene antas å være forskjellige.

Randomized-Select er Quicksort med ett rekursivt kall. Randomized-Partition velger en tilfeldig pivot og setter den på plass $q$, og da er pivoten det $k = q - p + 1$-ende minste i segmentet. Er $i = k$, er pivoten svaret. Er $i < k$, ligger svaret blant de små, og du søker etter rang $i$ der. Ellers ligger det blant de store, og der har det rang $i - k$, for $k$ elementer er allerede mindre. Som i binærsøk stopper du straks du treffer, og søker bare videre i én av delene.

from random import randint

def randomized_partition(A, p, r):
  j = randint(p, r)
  A[j], A[r] = A[r], A[j]
  return partition(A, p, r)

def randomized_select(A, p, r, i):
  if p == r:
      return A[p]
  q = randomized_partition(A, p, r)
  k = q - p + 1
  if i == k:
      return A[q]
  elif i < k:
      return randomized_select(A, p, q - 1, i)
  else:
      return randomized_select(A, q + 1, r, i - k)

Deler pivoten på midten hver gang, er $T(n) = T(n/2) + n$: ett kall på halve instansen pluss lineært arbeid til delingen.

Pivoten deler ikke på midten hver gang. Kall en pivot god når den har rang mellom $n/4$ og $3n/4$ i segmentet på $n$ elementer. Da har begge sidene høyst $3n/4$ elementer, så segmentet du søker videre i, har krympet til høyst $3/4$ av størrelsen. Halvparten av elementene er gode pivoter, så en tilfeldig pivot er god med sannsynlighet minst $1/2$. Som når du kaster mynt til første kron, trengs da i forventning høyst to forsøk, altså to delinger, før segmentet krymper slik. Hver deling koster høyst lineær tid i segmentet, så forventet arbeid er høyst

Dette betyr at forventet kjøretid er $\Theta(n)$ for enhver input, ettersom regningen bare bruker de tilfeldige valgene og ikke rekkefølgen i inputen. Verste tilfelle er som for Quicksort. Havner pivoten ytterst hver gang, er $T(n) = T(n-1) + n = \Theta(n^2)$, men det krever uflaks med de tilfeldige valgene, og ingen input er mer utsatt enn andre.

Randomized-Select(A, p, r, i)
1 if r ⩽ p
2     return A[p]
3 q = Randomized-Partition(A, p, r)
4 k = q − p + 1
5 if i == k
6     return A[q]
7 elseif i < k
8     Randomized-Select(A, p, q − 1, i)
9     Randomized-Select(A, q + 1, r, i − k)

8     return Randomized-Select(A, p, q − 1, i)
9 else return Randomized-Select(A, q + 1, r, i − k)

Select

Select fjerner tilfeldigheten og garanterer $\Theta(n)$ i verste tilfelle. Den bruker medianen av medianene til små grupper som pivot, og den pivoten ligger alltid nær midten.

1. Del i grupper på fem

   Del de $n$ elementene i $n/5$ grupper med fem i hver, og sorter hver gruppe. Fem elementer sorteres i konstant tid, så det koster $\Theta(n)$ til sammen. Er $n$ ikke delelig med fem, flyttes det minste elementet fremst og telles bort først, opptil fire ganger.

2. Finn medianen av medianene

   Hver gruppe har en median, det midterste av de fem. Kall Select rekursivt på de $n/5$ medianene og finn medianen av dem, $x$.

3. Del rundt $x$

   Bytt $x$ inn bakerst og kjør Partition. Nå står $x$ på plass $q$, og resten er som i Randomized-Select: svar, eller ett rekursivt kall på riktig side.

Garantien ligger i steg 2. Halvparten av gruppemedianene, $n/10$ av dem, er større enn eller lik $x$. Hver av dem og de to elementene over den i gruppen er større enn eller lik $x$, så minst $3 \cdot n/10$ elementer er større enn eller lik $x$. På samme måte er minst $3n/10$ elementer mindre enn eller lik $x$. Det rekursive kallet i steg 3 får derfor høyst $7n/10$ elementer.

Steg 2 er et rekursivt kall på $n/5$ elementer, steg 3 et kall på høyst $7n/10$, og gruppesorteringen og Partition koster $\Theta(n)$:

De to kallene får til sammen $9n/10$ elementer, mindre enn $n$, så arbeidet krymper geometrisk nedover i rekursjonstreet, og rota dominerer.

Select gir også de $k$ minste elementene i lineær tid: finn elementet med rang $k$ og del rundt det. Da står elementet på plass $k$ med de $k - 1$ mindre til venstre for seg, og de $k$ første plassene holder de $k$ minste. Konstanten i Select er stor, så i praksis brukes Randomized-Select. Select viser likevel at rangering kan gjøres i lineær tid også i verste tilfelle.

Stabilitet og Counting-Sort

Select og Randomized-Select går under sorteringsgrensen ved å be om mindre enn en sortert tabell. Den andre veien er å anta mer om inputen: verdiene er heltall i et lite område $0 .. k$. Da trenger du ikke sammenligne dem. Du kan bruke dem som indekser.

Elementer bærer ofte mer enn nøkkelen de sorteres på. Sorterer du en alfabetisk studentliste på karakter, kan studentene med samme karakter komme ut i en annen rekkefølge enn de sto i. En sorteringsalgoritme er stabil når like nøkler står i samme innbyrdes rekkefølge i output som i input, og da står studentene med samme karakter fortsatt alfabetisk. Når nøkkelen er hele elementet, spiller stabiliteten ingen rolle. Insertion-Sort og Merge-Sort er stabile når de skrives slik at et element flyttes bare forbi strengt større, og flettingen tar fra venstre ved likhet. Quicksort er det ikke, for Partition bytter elementer forbi hverandre.

Counting-Sort teller først hvor mange ganger hver verdi forekommer, $C[v]$. Så gjøres tellingen kumulativ, slik at $C[v]$ er antall elementer som er mindre enn eller lik $v$. I den sorterte tabellen $B$ står de $C[v-1]$ elementene som er mindre enn $v$, først, og $v$-ene fyller plassene etter dem, til og med plass nummer $C[v]$. Til slutt går du baklengs gjennom $A$: legg $A[j]$ på plass nummer $C[A[j]]$ i $B$, og trekk én fra $C[A[j]]$. Neste like verdi havner ett hakk til venstre.

def counting_sort(A, n, k):
  B = [None] * n
  C = [0] * (k + 1)
  for j in range(n):
      C[A[j]] = C[A[j]] + 1
  for i in range(1, k + 1):
      C[i] = C[i] + C[i - 1]
  for j in range(n - 1, -1, -1):
      C[A[j]] = C[A[j]] - 1  # plass nummer c har indeks c - 1
      B[C[A[j]]] = A[j]
  return B

Den baklengse løkka gjør algoritmen stabil. Den siste $v$-en i $A$ behandles først og får den siste plassen i sin blokk, og hver tidligere $v$ legges til venstre for den. Rekkefølgen fra $A$ er bevart. Kjøretiden er $\Theta(n + k)$, to løkker over $A$ og én over $C$. Er $k = O(n)$, er kjøretiden lineær. Sorteringsgrensen brytes ikke, for ingen elementer sammenlignes. Verdiene brukes som indekser, og indekseringen krever at de er små heltall.

Radix-Sort

Er verdiområdet stort, blir $C$ for stor. Men et tall med $d$ siffer har $d$ små nøkler. Radix-Sort sorterer stabilt på ett siffer om gangen, det minst signifikante først, med Counting-Sort med $k = 9$ som subrutine for desimale siffer.

def radix_sort(A, n, d):
  for i in range(d):
      A = stable_sort_on_digit(A, n, i)  # Counting-Sort med k = 9
  return A

Etter $i$ pass er tallene sortert på de $i$ siste sifrene. Denne invarianten holder ved induksjon, og induksjonssteget er stabiliteten. Pass nummer $i$ ordner tallene etter det $i$-ende sifferet bakfra. To tall med ulikt siffer der havner dermed i riktig rekkefølge, og to tall med likt siffer beholder rekkefølgen fra før, som var sortert på de $i - 1$ siste sifrene. Til sammen gir passet nøyaktig den rekkefølgen de $i$ siste sifrene gir.

Radix-Sort trenger begge deler: det minst signifikante sifferet først og en stabil subrutine. Starter du med det mest signifikante sifferet, ødelegger neste pass ordningen fra det forrige, for passet sorterer på et mindre viktig siffer uten å ta hensyn til det viktigere. Sorterer du 13 og 21 først på det fremste sifferet og så stabilt på det bakerste, ender du med 21, 13. Og er subrutinen ustabil, mister to tall med likt siffer ordningen fra de lavere sifrene.

Kjøretiden er $d$ pass med $\Theta(n + k)$ hver, altså $\Theta(d(n + k))$. Er $d$ og $k$ konstanter, som for sekssifrede desimaltall, er kjøretiden lineær. Et siffer trenger ikke være et desimalsiffer. Datoer sorteres stabilt på dag, så måned, så år. Etter hvert pass er datoene sortert på feltene som er behandlet, med samme induksjonssteg som for sifrene.

Bucket-Sort

Bucket-Sort antar at inputen er tilfeldige tall, uniformt fordelt i $[0, 1)$. Del intervallet i $n$ like bøtter, og legg $A[j]$ i bøtte nummer $\lfloor n \cdot A[j] \rfloor$. Det er hashing med kjeding, men hashfunksjonen bevarer ordningen: alt i bøtte $i$ er mindre enn alt i bøtte $i + 1$. Sorter hver bøtte med Insertion-Sort, og sett bøttene etter hverandre.

def bucket_sort(A, n):
  B = [[] for _ in range(n)]
  for j in range(n):
      B[int(n * A[j])].append(A[j])
  for i in range(n):
      insertion_sort(B[i], len(B[i]))
  return [x for bucket in B for x in bucket]

Insertion-Sort på en bøtte med $n_i$ elementer koster $O(n_i^2)$, så det er forventningen av $n_i^2$ som avgjør, ikke at bøtta i snitt får ett element. Med uniform fordeling havner hvert element i bøtte $i$ med sannsynlighet $1/n$, uavhengig av de andre, og da er $E[n_i^2] = 2 - 1/n$. Summert over de $n$ bøttene er forventet arbeid i Insertion-Sort $O(n)$, så hele sorteringen tar forventet $\Theta(n)$.

Forventningen her er et snitt over tilfeldige inputer, altså gjennomsnittstilfellet. Bucket-Sort gjør ingen tilfeldige valg selv, så en input der alt havner i én bøtte, gir alltid Insertion-Sort på hele inputen, $\Theta(n^2)$. Randomized-Select og Randomized-Quicksort har forventet kjøretid over sine egne tilfeldige valg, for enhver input, og den garantien er sterkere.

Sjekk deg selv