Quicksort forklart: partition, kjøretid og randomisering

Quicksort er en algoritme som sorterer verdier, for eksempel tall fra minst til størst. Den velger én verdi som delepunkt og sorterer delene hver for seg. Her får du prinsippet og pseudokoden forklart. Til slutt ser vi på tidskompleksitet, altså hvordan arbeidsmengden øker når listen blir lengre.

Ideen: splitt og hersk

Prinsippet kalles «splitt og hersk», eller divide and conquer: del opp problemet og løs de mindre delene.

Du velger ett element som pivot, altså verdien du deler rundt. I varianten vi viser her, flyttes elementer som er mindre enn eller lik pivot, til venstre. Større elementer flyttes til høyre. Samlingen med verdier kalles et array; du kan tenke på det som en liste.

Etter delingen står pivoten på en plass den kan ha i den ferdig sorterte listen. Så sorteres venstre og høyre del på samme måte. Dette kalles rekursjon: funksjonen kaller seg selv på mindre deler.

Algoritmen består altså av to deler: partition, som deler arrayet rundt en pivot, og de rekursive kallene på delarrayene.

Partition

PARTITION får et array A og to indekser, p og r. En indeks angir en plass i arrayet. Funksjonen deler området fra og med A[p] til og med A[r]. Koden under er pseudokode: den viser fremgangsmåten, men er ikke skrevet for å kjøres direkte i Python.

Her bruker vi Lomutos variant av partition. Den velger siste element, A[r], som pivot. Vi kaller pivotverdien x. Andre quicksort-varianter kan dele opp arrayet på andre måter.

Variabelen i markerer slutten på området med elementer som er mindre enn eller lik pivot. Variabelen j går gjennom arrayet fra venstre mot høyre.

Hver gang løkken finner et element A[j] som er mindre enn eller lik pivot, økes i med én, og A[i] byttes med A[j]. Elementet flyttes dermed inn i venstre del.

Til slutt byttes pivoten inn på plassen rett etter de små elementene. Funksjonen returnerer indeksen til denne plassen. For eksempel blir [4, 2, 5, 1, 3] til [2, 1, 3, 4, 5] når 3 er pivot i denne varianten. Pivoten står riktig, men delene må fortsatt sorteres hver for seg.

PARTITION(A, p, r)
  x = A[r]
  i = p - 1
  for j = p to r - 1
    if A[j] <= x
      i = i + 1
      bytt A[i] og A[j]
  bytt A[i + 1] og A[r]
  return i + 1

Kjøretiden til partition

Løkken går fra p til r − 1 og besøker dermed alle elementene unntatt pivoten én gang. Hver runde gjør et begrenset antall operasjoner: en sammenligning og eventuelt et bytte.

For n elementer vokser arbeidsmengden omtrent i takt med n. Dette kalles lineær kjøretid og skrives Θ(n). Symbolet Θ beskriver vekstordenen, ikke antall sekunder.

Selve quicksort

QUICKSORT(A, p, r)
  if p < r
    q = PARTITION(A, p, r)
    QUICKSORT(A, p, q - 1)
    QUICKSORT(A, q + 1, r)

Først deler PARTITION arrayet og gir pivotens posisjon q. Deretter kaller QUICKSORT seg selv på venstre og høyre del. Betingelsen p < r sørger for at den stopper når en del har null eller ett element.

Legg merke til at pivoten på plass q holdes utenfor begge de rekursive kallene. Den er allerede der den skal være.

Kjøretid i beste tilfelle

Kjøretiden avhenger sterkt av hvor balansert partition blir.

I beste tilfelle deler pivoten arrayet omtrent på midten. La T(n) beskrive arbeidsmengden for n elementer. Vi kan beskrive den med denne forenklede rekurrenslikningen:

T(n) = 2T(n/2) + Θ(n)

De to halvdelene gir omtrent 2T(n/2), mens selve delingen gir Θ(n). Ser vi på alle nivåene samlet, får vi:

T(n) = Θ(n log n)

Det betyr at arbeidsmengden vokser raskere enn n, men langsommere enn n². Mergesort er en annen sorteringsalgoritme med kjøretid Θ(n log n).

Verste tilfelle

I verste tilfelle havner nesten alle elementene på samme side av pivoten hver gang: én del får n − 1 elementer, og den andre blir tom.

T(n) = T(n − 1) + Θ(n)

Dette løser til:

T(n) = Θ(n²)

Dette skjer for eksempel med en allerede sortert liste når siste element alltid velges som pivot. Det skjer også når alle verdiene er like i partition-varianten vi bruker her.

Hvorfor quicksort likevel er rask

Du trenger ikke perfekte delinger for å få n log n.

Selv en gjentatt deling på omtrent 10 og 90 prosent gir Θ(n log n). Det blir flere nivåer enn ved halvering, men antallet nivåer vokser fortsatt omtrent som log n.

Problemet er altså ikke enhver skjev deling. Det oppstår når en del stadig beholder nesten alle elementene, som n − 1 av n, slik at problemet krymper svært lite for hvert kall.

Randomisert quicksort

Tilfeldig pivotvalg kan redusere risikoen for gjentatte dårlige delinger som skyldes rekkefølgen på verdiene.

RANDOMIZED-PARTITION(A, p, r)
  i = RANDOM(p, r)
  bytt A[i] og A[r]
  return PARTITION(A, p, r)

Velg en indeks tilfeldig, med lik sannsynlighet for alle plasser fra p til r. Bytt dette elementet med A[r], og kjør deretter samme PARTITION som før. Da er pivoten tilfeldig valgt.

RANDOMIZED-QUICKSORT(A, p, r)
  if p < r
    q = RANDOMIZED-PARTITION(A, p, r)
    RANDOMIZED-QUICKSORT(A, p, q - 1)
    RANDOMIZED-QUICKSORT(A, q + 1, r)

Forventet kjøretid

Forventet kjøretid er et gjennomsnitt over de tilfeldige pivotvalgene, ikke en garanti for hvert enkelt forsøk.

Når alle verdiene er ulike og pivoten velges jevnt tilfeldig, er forventet antall sammenligninger Θ(n log n). Dette gjelder uansett den opprinnelige rekkefølgen.

Med ulike verdier: forventet kjøretid Θ(n log n), verste kjøretid Θ(n²).

Verste tilfelle er fortsatt mulig. For ulike verdier blir det imidlertid lite sannsynlig å velge et ytterpunkt som pivot om og om igjen.

Randomisering løser ikke alle problemer. Med mange like verdier kan Lomutos variant fortsatt gi svært skjeve delinger. Er alle verdiene like, blir kjøretiden Θ(n²), også med tilfeldig pivot. En tredelt partition, med grupper for mindre, lik og større enn pivot, kan håndtere like verdier bedre.

Kort oppsummert

Quicksort deler arrayet rundt en pivot og sorterer delene rekursivt. Partition-varianten her bruker lineær tid. Omtrent balanserte delinger gir Θ(n log n), mens gjentatte delinger i n − 1 og 0 gir Θ(n²). Tilfeldig pivot gir forventet Θ(n log n) for ulike verdier. Ved mange like verdier må du også ta hensyn til hvordan partition er laget.

Se forklaringen på video

Vil du se temaet forklart? Åpne videoleksjonen «Quicksort» i EnkelEksamen. Du må logge inn, og enkelte leksjoner krever tilgang til faget.

Vil du jobbe videre med faget? Se innholdet i Algoritmer og datastrukturer ved NTNU, eller finn faget som passer til ditt studiested.

Vil du lese mer om programmering, har vi også en artikkel om objektorientert programmering.