Rangering i lineær tid

Alle sorteringene vi har sett — Insertion-, Merge- og Quicksort — bestemmer rekkefølgen ved å sammenligne elementer. Det er ikke tilfeldig at ingen av dem slår $n \lg n$: det finnes en prinsipiell nedre grense for sammenligningsmodellen. Antar vi derimot mer om inputen, kan vi sortere i lineær tid.

Den nedre grensen for sammenligningssortering

Tenk på en sammenligningssortering som et beslutningstre: hver indre node er en sammenligning «$a_i \le a_j$?» med to utganger, og hvert blad er én av de mulige sorterte rekkefølgene. Et binært tre med høyde $h$ har høyst $2^h$ blader, og vi trenger ett blad per mulig permutasjon — altså $2^h \ge n!$. Løser vi for $h$ og bruker Stirlings approksimasjon, får vi worst-case-grensen.

Grensen gjelder kun sammenligningsbaserte algoritmer. Merge-Sort og randomisert Quicksort treffer den (og er dermed asymptotisk optimale i denne modellen), mens de kvadratiske sorteringene ligger godt over.

Stabilitet

Stabilitet virker som en detalj, men den er selve forutsetningen for at Radix-Sort skal fungere. Insertion- og Merge-Sort er naturlig stabile; Selection- og Quicksort er det ikke (de flytter elementer over lange avstander).

To kvadratiske sammenligningssorteringer

For å se kontrasten til de lineære sorteringene er det nyttig å ha to enkle sammenligningssorteringer friskt i minne. Selection-Sort bygger en sortert prefiks ved gjentatte ganger å hente minimumet av den usorterte halen:

def selection_sort(a: list[int]) -> list[int]:
  n = len(a)
  for i in range(n):
      m = i
      for j in range(i + 1, n):
          if a[j] < a[m]:
              m = j
      a[i], a[m] = a[m], a[i]
  return a

Selection-Sort gjør alltid $\Theta(n^2)$ sammenligninger — den er ikke adaptiv. Bubble-Sort gjør i stedet lokale nabobytter, slik at det største usorterte elementet «bobler» til høyre i hver runde:

def bubble_sort(a: list[int]) -> list[int]:
  n = len(a)
  for i in range(n):
      for j in range(n - i - 1):
          if a[j] > a[j + 1]:
              a[j], a[j + 1] = a[j + 1], a[j]
  return a

Lineær tid ved å anta mer

Counting-Sort sorterer heltall i et lite område $\{0, \dots, k\}$ uten en eneste sammenligning: tell forekomstene av hver nøkkel, gjør tellingene om til posisjoner ved en prefikssum, og plasser hvert element direkte. Det koster $\Theta(n + k)$, som er lineært når $k = O(n)$. Ved å fylle output fra høyre mot venstre blir Counting-Sort stabil.

Radix-Sort sorterer flersifrede nøkler ett siffer av gangen, fra minst til mest signifikante siffer, med en stabil Counting-Sort som subrutine på hvert siffer. Her er stabiliteten ikke valgfri:

Bucket-Sort utnytter at input er tilnærmet jevnt fordelt: fordel elementene i $n$ bøtter etter verdi, sorter hver bøtte (typisk med Insertion-Sort), og les bøttene i rekkefølge. Med jevn fordeling blir hver bøtte liten i forventning, og den forventede kjøretiden blir $\Theta(n)$.

Å finne det k-te minste — Select

Skal du bare ha det $k$-te minste elementet (for eksempel medianen), trenger du ikke sortere hele tabellen. Randomized-Select gjenbruker Quicksorts partisjonering, men rekurserer bare på den ene siden der det $k$-te elementet ligger. Det gir forventet lineær tid, $\Theta(n)$ — vi sparer den logaritmiske faktoren fordi vi kaster bort den halvdelen vi ikke trenger.

Select (median-of-medians) velger pivoten smart nok til å garantere en balansert partisjon, og oppnår $\Theta(n)$ worst-case. Begge brukes til å hente de $k$ minste elementene: finn grenseverdien på plass $k$, og alt til venstre for den er svaret.

Sjekk deg selv