2.1 Sammenligningsbaserte sorteringer

`Insertion-Sort`, `Merge-Sort`, `Quicksort` og `Randomized-Quicksort` — mekanikk, kjøretider (beste/verste/forventet) og `Θ(n\lg n)`-nedre grensen.

55 min

9 oppgaver

Sammenligningsbaserte sorteringer

Din fremgang i kapitlet

0 / 9 oppgaver

Kapitlets plass i kurset

Bygger på

1.4Rekurrenser — masterteoremet

Brukes videre i

2.2Lineær sortering og stabilitet 2.3Utvelgelse — Partition, Randomized-Select og Select 3.1Hauger og Heapsort

Sortering er registrert i alle de 17 settene i grunnlaget (100 %). Grunnlaget
er de 17 settene fra august 2015 til august 2023 som er gjennomgått tema for
tema — det er nevneren hver gang boka oppgir en prosent. Ingen andre temaer
slår det, og bare to andre er like høye (asymptotisk notasjon og
NP/reduksjoner).

Temaet kommer i to sjangre, og de skrives ut i klarspråk her:

- Sjanger E — kjøretidskunnskap, altså at du oppgir kjøretiden til en
navngitt algoritme i det strammeste uttrykket som er riktig. Spørsmålet er
ofte spisset: «beste tilfelle», «verste tilfelle», «forventet» — og de tre
har ulike svar for tre av de fire algoritmene i dette kapitlet.
- Sjanger C — håndkjøring, altså at du utfører algoritmen steg for steg på
papir og oppgir bare sluttilstanden. Selve håndkjøringsdrillen ligger i
kap. 2.4; her møter du mekanikken første gang.

Høyeste prioritet — dette må sitte. Eksamen er hjelpemiddelfri, så
kjøretidstabellen nederst i kapitlet er rent puggestoff.

To ting er verdt å merke seg med én gang:

1. Skillet mellom garantert og inputavhengig kjøretid er selve poenget.
Merge-Sort er $\Theta(n\lg n)$ uansett hva du gir den. Quicksort er
$\Theta(n\lg n)$ forventet og $\Theta(n^2)$ i verste tilfelle. Å svare
« $\Theta(n\lg n)$ » på et spørsmål om Quicksorts verste tilfelle er galt,
selv om tallet stemmer for det vanlige tilfellet.
2. Den nedre grensen $\Omega(n\lg n)$ gjelder bare sortering som
sammenligner elementer med hverandre. Kap. 2.2
viser sorteringer som går i lineær tid nettopp fordi de ikke sammenligner.

Slik er kapitlet lagt opp (55 min):

Innhold	Tid
`Insertion-Sort` og løkkeinvarianten	ca. 12 min
`Merge-Sort` og rekurrensen bak den	ca. 14 min
`Quicksort` og pivotens rolle	ca. 13 min
`Randomized-Quicksort`	ca. 6 min
Den nedre grensen for sammenligningssortering	ca. 10 min

Forkunnskaper

- kap. 1.1 — de asymptotiske symbolene. Du trenger
skillet mellom $O$ (bare øvre grense er vist), $\Omega$ (bare nedre) og
$\Theta$ (tett grense begge veier), fordi dette kapitlet bruker alle tre
bevisst. I hele boka betyr $\lg n$ det samme som $\log_2 n$ .
- kap. 1.2 — forenkling. Kjøretidssvar oppgis alltid i
det strammeste uttrykket som er riktig.
- kap. 1.4 — masterteoremet. Merge-Sorts kjøretid
utledes her ved å løse rekurrensen $T(n) = 2T(n/2) + \Theta(n)$ , og det gjør
vi med masterteoremet.

Vil du se sortering konkret i kode først, er
Sortering: boblesortering, .sort() og gitt sort_list
et mykere første møte. Du trenger ikke mer enn å kunne følge en løkke med
blyant.

Notasjons- og pseudokodeliste

`Insertion-Sort` og løkkeinvarianten (~12 min)

Du har fjorten pasientjournaler i en bunke og skal legge dem i stigende
rekkefølge etter registreringsnummer. Den naturlige framgangsmåten er å ta én
journal av gangen, holde den i hånden, og skyve den inn på riktig plass i den
delen av bunken du allerede har ordnet. Det er nøyaktig Insertion-Sort.

Algoritmen er interessant på eksamen av to grunner. Den er den ene sorteringen
som er raskere på pen input — allerede sortert input gir lineær tid — og
den er den letteste å begrunne, fordi begrunnelsen er en løkkeinvariant:
en påstand om tilstanden som er sann før løkka begynner, forblir sann gjennom
hver runde, og gir det du vil ha når løkka er ferdig.

Løkkeinvariant

En løkkeinvariant er en påstand om tilstanden som gjelder rett før hver runde i en løkke. Den brukes til å vise at en algoritme er riktig, og har alltid tre ledd: initialisering (påstanden er sann før første runde), vedlikehold (er den sann før en runde, er den sann før den neste), og terminering (når løkka stopper, gir påstanden nettopp det resultatet vi ville ha). Ordet «invariant» betyr her det som ikke endrer seg — ikke tilstanden selv, men påstanden om den.

📜Pseudokode-kontrakt: `Insertion-Sort`

Antagelser om representasjon. Arrayet er A[1..n], indeks fra 1.
Elementene kan sammenlignes med < og >; ingenting annet antas om dem.
Sorteringen skjer på stedet (in-place): utenom noen få hjelpevariabler
brukes ingen ekstra plass som vokser med

n

Prebetingelse: A[1..n] inneholder $n$ elementer i vilkårlig rekkefølge.
Postbetingelse: A[1..n] inneholder de samme elementene i stigende
rekkefølge.

Insertion-Sort(A)
  Input:  array A[1..n]
  Output: A sortert stigende, paa stedet
  for j = 2 to A.length
      key = A[j]
      i = j - 1
      while i >= 1 and A[i] > key
          A[i+1] = A[i]
          i = i - 1
      A[i+1] = key
  Kjoeretid: Theta(n) beste, Theta(n^2) verste

Invarianten i én setning: rett før hver runde med indeks j er
A[1..j-1] sortert og inneholder nøyaktig de elementene som lå der fra start.

Kjøretid: den ytre løkka går $n-1$ ganger. Den indre while-løkka gjør
ingen runder når A[j] allerede er større enn alt til venstre — da blir
totalen $\Theta(n)$ . Er arrayet sortert synkende, må hvert element skyves
helt fram til indeks 1, og totalen blir $1 + 2 + \dots + (n-1) = n(n-1)/2$ ,
altså $\Theta(n^2)$ .

✏️Eksempel 1: `Insertion-Sort` runde for runde

Seks måleverdier fra en værstasjon ligger i den rekkefølgen de ble avlest:
A = 34, 12, 47, 8, 23, 19 (indeks fra 1).

Kjør Insertion-Sort(A) og oppgi arrayet etter hver runde i den ytre løkka.
Tell til slutt hvor mange enkeltskyv den indre løkka gjorde til sammen.

Løkka starter på $j = 2$ , fordi A[1..1] er sortert allerede.

Runde `j`	`key`	Antall skyv i while-løkka	Array etter runden
2	12	1	`12, 34, 47, 8, 23, 19`
3	47	0	`12, 34, 47, 8, 23, 19`
4	8	3	`8, 12, 34, 47, 23, 19`
5	23	2	`8, 12, 23, 34, 47, 19`
6	19	3	`8, 12, 19, 23, 34, 47`

Til sammen 9 skyv i den indre løkka.
Sluttilstanden — det du ville levert på eksamen:
8, 12, 19, 23, 34, 47
Legg merke til runde 3: key = 47 er større enn alt til venstre, så while-løkka
gjør null runder. Det er nettopp det som skjer i hver runde når inputen
allerede er sortert, og det er derfor beste tilfelle er

\Theta(n)

På eksamen leverer du bare sluttarrayet — tavlen er her for å vise hvordan du

kommer dit.

📝Oppgave 1

(Innstegsoppgave, sjanger D — definisjon med egne ord, altså én presis setning
med hovedpoenget først.)

Hva er beste tilfelle for Insertion-Sort, hvilken input gir det, og hva er
verste tilfelle?

📝Oppgave 2

Sjanger C

Kjør Insertion-Sort på A = 5, 3, 9, 1 og oppgi arrayet etter hver runde i
den ytre løkka.

`Merge-Sort` og rekurrensen bak den (~14 min)

Insertion-Sort bruker kvadratisk tid på store arrayer, og det er for dyrt.
Den andre ideen er splitt og hersk: del arrayet i to like store halvdeler,
sorter hver halvdel for seg, og flett de to sorterte halvdelene sammen. Selve
arbeidet ligger i flettingen.

Flettingen er lettere enn den ser ut. Har du to sorterte bunker foran deg, er
det minste elementet i unionen alltid det øverste i én av de to bunkene. Du
sammenligner de to toppene, tar den minste, og gjentar.

📜Pseudokode-kontrakt: `Merge`

Antagelser om representasjon. Arrayet er A[1..n], indeks fra 1.
Indeksene tilfredsstiller p <= q < r. Rutinen bruker to hjelpearrayer L og
R, og er derfor ikke på stedet.

Prebetingelse: A[p..q] er sortert, og A[q+1..r] er sortert.
Postbetingelse: A[p..r] er sortert og inneholder de samme elementene.

Merge(A, p, q, r)
  Input:  A[p..q] og A[q+1..r] er hver for seg sorterte
  Output: A[p..r] sortert
  kopier A[p..q] til L og A[q+1..r] til R
  legg en vaktpost stoerre enn alle elementer bakerst i L og i R
  i = 1
  j = 1
  for k = p to r
      if L[i] <= R[j]
          A[k] = L[i]
          i = i + 1
      else
          A[k] = R[j]
          j = j + 1
  Kjoeretid: Theta(r - p + 1)

Invarianten i én setning: rett før hver runde med indeks k inneholder
A[p..k-1] de $k-p$ minste elementene fra L og R, i sortert rekkefølge,
og L[i] og R[j] er de minste elementene som ennå ikke er kopiert tilbake.

Merk <= og ikke < i testen. Ved likhet plukkes elementet fra
venstre bunke først. Det er den lille detaljen som gjør Merge-Sort
stabil: like elementer beholder sin innbyrdes rekkefølge, fordi venstre
bunke lå først i arrayet.

Kjøretid: hver runde i for-løkka plasserer nøyaktig ett element, og det er
$r-p+1$ elementer å plassere — altså $\Theta(r-p+1)$ , lineært i lengden på
delen som flettes.

✏️Eksempel 2: Flettesteget, sammenligning for sammenligning

To sorterte halvdeler skal flettes: venstre er 2, 5, 9, høyre er
3, 4, 11.

Utfør Merge og oppgi hvilken sammenligning som gjøres i hvert steg, og hvor
mange sammenligninger flettingen koster til sammen.

Steg	Sammenligning	Plukket	`A` etter steget
1	2 mot 3	2 (venstre)	`2`
2	5 mot 3	3 (høyre)	`2, 3`
3	5 mot 4	4 (høyre)	`2, 3, 4`
4	5 mot 11	5 (venstre)	`2, 3, 4, 5`
5	9 mot 11	9 (venstre)	`2, 3, 4, 5, 9`
6	venstre bunke tom	11 (høyre)	`2, 3, 4, 5, 9, 11`

Sluttilstanden: 2, 3, 4, 5, 9, 11.
Seks elementer ut, men bare fem sammenligninger: det siste steget trenger
ingen, fordi den ene bunken er tom og resten kan kopieres rett over. Generelt
koster fletting av

n

elementer høyst

n-1

sammenligninger og nøyaktig

n

plasseringer — begge deler

\Theta(n)

.
Legg merke til at ingen sammenligning noen gang involverer to elementer fra
samme bunke. De er allerede innbyrdes sortert, og den informasjonen kastes

ikke bort. Det er hele gevinsten ved splitt og hersk.

📜Pseudokode-kontrakt: `Merge-Sort`

Antagelser om representasjon. Arrayet er A[1..n], indeks fra 1. Kallet
utenfra er Merge-Sort(A, 1, A.length). Rutinen krever hjelpeplass på

\Theta(n)

celler til flettingen, og går derfor ikke på stedet.

Prebetingelse: p <= r, og A[p..r] inneholder elementene som skal
sorteres.
Postbetingelse: A[p..r] er sortert stigende.

Merge-Sort(A, p, r)
  Input:  array A[p..r]
  Output: A[p..r] sortert stigende
  if p < r
      q = floor((p + r) / 2)
      Merge-Sort(A, p, q)
      Merge-Sort(A, q+1, r)
      Merge(A, p, q, r)
  Kjoeretid: Theta(n lg n)

Grunnideen i én setning: en del med ett element er sortert per definisjon,
og to sorterte deler kan flettes til én sortert del i lineær tid — altså
holder det å halvere seg ned til enkeltelementer og flette seg opp igjen.

Kjøretid: delingen koster konstant tid, de to rekursive kallene er hver på
halvparten så stor input, og flettingen koster $\Theta(n)$ . Det gir

$T(n) = 2T(n/2) + \Theta(n)$

Her er $a = 2$ og $b = 2$ , så $n^{\log_b a} = n^{\log_2 2} = n^1$ . Siden
$f(n) = \Theta(n) = \Theta(n^{\log_b a}\lg^{0} n)$ , treffer vi tilfelle 2
i masterteoremet med $k = 0$ , og svaret blir $T(n) = \Theta(n^{1}\lg^{1} n) = \Theta(n\lg n)$ . Ingen input gjør den raskere, og ingen gjør den tregere:
grensen er tett begge veier.

Det er lett å tro at logaritmefaktoren i tilfelle 2 må være der fra før for at
tilfellet skal gjelde. Det må den ikke.

Pensumvarianten av tilfelle 2 er $f(n) = \Theta(n^{\log_b a}\lg^{k} n)$ med
$k \ge 0$ — ikke-negativ, altså. Merge-Sort har $k = 0$ , og faller midt
inne i tilfellet. Svaret får da nøyaktig én logaritmefaktor: $\lg^{k+1} n = \lg n$ .

Det dokumenterte unntaket går den andre veien: en rekurrens som svarer til
negativ $k$ , for eksempel $T(n) = 2T(n/2) + n/\lg n$ , faller utenfor
pensumvarianten. Se kap. 1.4.

📝Oppgave 3

Eksamensnivå, sjanger B

En sorteringsrutine deler arrayet i tre like store deler, sorterer hver av
dem rekursivt, og fletter de tre sorterte delene i lineær tid.

a) Sett opp rekurrensen.
b) Løs den, og navngi metoden.

📝Oppgave 4

Eksamensnivå, sjanger F

Ta stilling til hver av påstandene:

a) Merge-Sort sorterer på stedet.
b) Merge-Sort er stabil.
c) Merge-Sort er raskere på et allerede sortert array enn på et
tilfeldig array.

`Quicksort` og pivotens rolle (~13 min)

Merge-Sort deler alltid midt på, og betaler for det med hjelpeplass.
Quicksort snur det: den deler etter verdi i stedet for etter posisjon, og
slipper dermed flettingen helt. Prisen er at delingen kan bli skjev.

Delingen gjøres av Partition. Den velger et element som pivot — et
skilleelement — og stokker om delen slik at alt som er mindre enn eller lik
pivoten havner til venstre for den, og alt som er større havner til høyre.
Etterpå står pivoten på sin endelige plass, og de to sidene kan sorteres
uavhengig. Mekanikken i Partition tas i detalj i
kap. 2.3; her trenger du kontrakten.

Pivot

Et pivot er skilleelementet en partisjonering deler om. Etter Partition(A, p, r) står pivoten på en indeks q slik at alt i A[p..q-1] er mindre enn eller lik pivoten, og alt i A[q+1..r] er større. Pivoten selv er da ferdig plassert og røres aldri igjen. I denne boka velger Partition siste element i delen som pivot, slik CLRS gjør. Randomized-Partition bytter først et tilfeldig element inn på siste plass, og kaller så Partition .

📜Pseudokode-kontrakt: `Quicksort`

Antagelser om representasjon. Arrayet er A[1..n], indeks fra 1. Kallet
utenfra er Quicksort(A, 1, A.length). Partition(A, p, r) bruker siste
element A[r] som pivot og returnerer pivotens sluttindeks q. Sorteringen
går på stedet.

Prebetingelse: A[p..r] inneholder elementene som skal sorteres.
Postbetingelse: A[p..r] er sortert stigende.

Quicksort(A, p, r)
  Input:  array A[p..r]
  Output: A[p..r] sortert stigende, paa stedet
  if p < r
      q = Partition(A, p, r)
      Quicksort(A, p, q-1)
      Quicksort(A, q+1, r)
  Kjoeretid: Theta(n lg n) forventet, Theta(n^2) verste

Grunnideen i én setning: når pivoten står på sin endelige plass, er
problemet redusert til to uavhengige, mindre sorteringsproblemer — og ingen
fletting trengs etterpå, fordi rekkefølgen mellom de to sidene allerede er
riktig.

Kjøretid: partisjoneringen av en del med $m$ elementer koster
$\Theta(m)$ . Blir delingen jevn, får vi $T(n) = 2T(n/2) + \Theta(n) = \Theta(n\lg n)$ . Blir den maksimalt skjev — pivoten er alltid det største
eller minste elementet — får vi $T(n) = T(n-1) + \Theta(n)$ , som gir
$\Theta(n^2)$ . Det verste tilfellet inntreffer nettopp på et allerede
sortert array når pivoten er siste element.

✏️Eksempel 3: `Quicksort` kall for kall

Sju ordrenumre ligger i mottaksrekkefølge: A = 26, 9, 41, 17, 33, 12, 22
(indeks fra 1).

Kjør Quicksort(A, 1, 7) med siste element som pivot. Oppgi arrayet etter
hver partisjonering, og hvor dypt rekursjonen går.

Bare kall som faktisk partisjonerer er tatt med; kall på deler med null eller
ett element gjør ingenting.

Kall	Del	Pivot	`q`	Array etter partisjoneringen
`Quicksort(A, 1, 7)`	`A[1..7]`	22	4	`9, 17, 12, 22, 33, 41, 26`
`Quicksort(A, 1, 3)`	`A[1..3]`	12	2	`9, 12, 17, 22, 33, 41, 26`
`Quicksort(A, 5, 7)`	`A[5..7]`	26	5	`9, 12, 17, 22, 26, 41, 33`
`Quicksort(A, 6, 7)`	`A[6..7]`	33	6	`9, 12, 17, 22, 26, 33, 41`

Sluttilstanden: 9, 12, 17, 22, 26, 33, 41.
Dybden er 3: kallet på hele arrayet, deretter på A[5..7], deretter på
A[6..7]. Fire partisjoneringer til sammen på sju elementer.
Legg merke til den første delingen. Pivoten 22 havnet på indeks 4, altså
nesten midt på — det er den heldige varianten. Hadde arrayet vært

9, 12, 17, 22, 26, 33, 41 fra start, ville hver pivot vært det største

elementet i sin del, hver deling ville skilt av nøyaktig ett element, og
dybden ville blitt 6 i stedet for 3.

📝Oppgave 5

Eksamensnivå, sjanger E

a) Hva er verste-tilfelle-kjøretiden til Quicksort med siste element som
pivot, og på hvilken input oppstår den?
b) Hva er kjøretiden i det vanlige tilfellet, og hvilket symbol hører til
det svaret?

`Randomized-Quicksort` (~6 min)

Problemet med Quicksort er ikke at det finnes en dårlig input — det er at
den dårlige inputen er vanlig. Sorterte og nesten sorterte data dukker opp
overalt.

Løsningen er å flytte tilfeldigheten fra inputen til algoritmen. I stedet for
alltid å ta siste element som pivot, trekker Randomized-Partition et
tilfeldig element i delen, bytter det til siste plass, og partisjonerer som
før.

📜Pseudokode-kontrakt: `Randomized-Quicksort`

Antagelser om representasjon. Som Quicksort: A[1..n], indeks fra 1, på
stedet. Random(p, r) returnerer et tilfeldig heltall i [p, r], hvert like
sannsynlig.

Prebetingelse: A[p..r] inneholder elementene som skal sorteres.
Postbetingelse: A[p..r] er sortert stigende. Resultatet er alltid
riktig; det er bare kjøretiden som avhenger av de tilfeldige trekkene.

Randomized-Partition(A, p, r)
  Input:  array A[p..r]
  Output: pivotens sluttindeks q
  i = Random(p, r)
  bytt A[i] og A[r]
  return Partition(A, p, r)

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)
  Kjoeretid: Theta(n lg n) forventet, uansett input

Grunnideen i én setning: når pivoten trekkes tilfeldig, er sannsynligheten
for en rimelig jevn deling stor i hvert kall, og forventningen over alle
trekkene blir $\Theta(n\lg n)$ — uten at noen bestemt input kan framtvinge det
dårlige tilfellet.

Kjøretid: $\Theta(n\lg n)$ forventet, for enhver input. Verste
tilfelle er fortsatt $\Theta(n^2)$ — trekker du uheldig hver eneste gang, går
det like galt — men nå er «uheldig» et spørsmål om terningkast, ikke om hvem
som leverte dataene.

Typiske feil

De to første koster hele oppgaven.

- Å oppgi feil kjøretidsfakta. Dette er felle #9 — å bomme på et tall
som skal kunnes utenat. De to hyppigste er å påstå at Insertion-Sort har
$\Omega(n\lg n)$ i beste tilfelle (den er $\Theta(n)$ ), og å oppgi
Quicksorts forventede kjøretid som svar på et spørsmål om verste tilfelle.
Kontrollen: les spørsmålet én gang til og finn ordet «beste», «verste» eller
«forventet».
- Å blande garantert og inputavhengig. Merge-Sort er $\Theta(n\lg n)$
uansett; Quicksort er $\Theta(n\lg n)$ forventet. Ordet «forventet» er
ikke en høflighetsfrase — det er forskjellen mellom en garanti og et
gjennomsnitt.
- Å tro at Merge-Sort går på stedet. Flettingen krever hjelpearrayer på
$\Theta(n)$ celler. Quicksort, Heapsort og Insertion-Sort går på
stedet; Merge-Sort gjør det ikke.
- Å bruke $\Omega(n\lg n)$ -grensen på alt. Grensen gjelder bare
sorteringer som avgjør rekkefølgen ved å sammenligne elementer med
hverandre. Kap. 2.2 viser sorteringer som går i
lineær tid fordi de bruker nøkkelverdiene direkte.
- Å påstå at Randomized-Quicksort er garantert $\Theta(n\lg n)$ . Verste
tilfelle er fortsatt $\Theta(n^2)$ . Det som er nytt, er at ingen input kan
framtvinge det.

Og den gjennomgående: å oppgi $\Theta$ der bare $O$ er vist. Har du bare
begrunnet en øvre grense, skriv $O$ .

Den nedre grensen for sammenligningssortering (~10 min)

Alle fire algoritmene over har det til felles at de bare stiller ett slags
spørsmål om dataene: «er dette elementet mindre enn hint?» De kan flytte
elementer rundt, men de kan aldri se på verdien og regne ut hvor den hører
hjemme. Slike algoritmer kalles sammenligningsbaserte.

Det setter en grense som ingen smartere idé kan komme under, og grensen er
verdt å kunne argumentere for på tre linjer.

Sammenligningsbasert sortering

a_i \le a_j

📜Nedre grense:

\Omega(n\lg n)

for sammenligningssortering

Påstanden. Enhver sammenligningsbasert sortering bruker

\Omega(n\lg n)

sammenligninger i verste tilfelle.

Argumentet, kort. Kjøringen kan tegnes som et beslutningstre: hver
indre node er én sammenligning, og de to grenene er de to svarene. Hver
løvnode er én mulig utgangsrekkefølge av elementene.

Med $n$ forskjellige elementer finnes $n!$ mulige rekkefølger, og algoritmen
må kunne ende opp i hver av dem — ellers finnes en input den sorterer feil.
Altså har treet minst $n!$ løvnoder.

Et binært tre med høyde $h$ har høyst $2^h$ løvnoder. Da må $2^h \ge n!$ ,
altså $h \ge \lg(n!)$ . Og $\lg(n!) = \Theta(n\lg n)$ : minst halvparten av
faktorene i $n!$ er større enn $n/2$ , så $n! \ge (n/2)^{n/2}$ , som gir
$\lg(n!) \ge (n/2)\lg(n/2) = \Omega(n\lg n)$ .

Høyden er antall sammenligninger i verste tilfelle, altså er den
$\Omega(n\lg n)$ .

Hva grensen ikke sier. Den sier ingenting om sorteringer som ikke
sammenligner, og den sier ingenting om beste tilfelle for en enkelt
algoritme. Merge-Sort og Heapsort når grensen, og er dermed
asymptotisk optimale blant sammenligningssorteringene.

📝Oppgave 6

Eksamensnivå, sjanger F

En kandidat skriver i besvarelsen sin: «Siden enhver sortering bruker minst
$\Omega(n\lg n)$ tid, kan ingen sortering være lineær.»

Er utsagnet riktig? Svar ja eller nei, og forklar kort.

📝Oppgave 7

Eksamensnivå, sjanger E

Fyll ut tabellen for de fire algoritmene i dette kapitlet.

Algoritme	Beste	Verste	På stedet?	Stabil?
`Insertion-Sort`
`Merge-Sort`
`Quicksort`
`Randomized-Quicksort`

📝Oppgave 8

Eksamensnivå, sjanger F

En kollega foreslår å forbedre Quicksort slik: «Før vi partisjonerer,
sjekker vi om delen allerede er sortert. Er den det, hopper vi over hele
rekursjonen. Da blir verste tilfelle $\Theta(n\lg n)$ .»

Stemmer konklusjonen? Svar ja eller nei, og begrunn.

📝Oppgave 9

Eksamensnivå, sjanger H

Et laboratorium har $n$ prøverør med hver sin måleverdi. Du skal finne ut om
to av rørene har nøyaktig samme verdi, og i så fall hvilke to.

Beskriv en algoritme som bruker $\Theta(n\lg n)$ tid, og forklar hvorfor
kjøretiden holder.

Kjøretidene samlet

Dette er kapitlets puggeflate. Eksamen er hjelpemiddelfri, så tabellen må ligge
i hodet.

Algoritme	Beste	Verste	Forventet	Krav / egenskap
`Insertion-Sort`	$\Theta(n)$	$\Theta(n^2)$	$\Theta(n^2)$	på stedet, stabil; beste tilfelle er ferdigsortert input
`Merge-Sort`	$\Theta(n\lg n)$	$\Theta(n\lg n)$	$\Theta(n\lg n)$	ikke på stedet ( $\Theta(n)$ hjelpeplass), stabil
`Quicksort`	$\Theta(n\lg n)$	$\Theta(n^2)$	$\Theta(n\lg n)$	på stedet, ustabil; verste tilfelle på sortert input
`Randomized-Quicksort`	$\Theta(n\lg n)$	$\Theta(n^2)$	$\Theta(n\lg n)$ for enhver input	på stedet, ustabil
`Merge` (ett flettesteg)	$\Theta(m)$	$\Theta(m)$	$\Theta(m)$	$m$ = antall elementer som flettes; krever to sorterte deler
`Partition` (ett steg)	$\Theta(m)$	$\Theta(m)$	$\Theta(m)$	ett gjennomløp, på stedet

Heapsort hører også hjemme i denne oversikten: den er

\Theta(n\lg n)

garantert, går på stedet og er ustabil. Haugstrukturen den bygger på, tas i
kap. 3.1.
Én presisering som er verdt å ta med seg. Ingen av de fire kan komme under

\Omega(n\lg n)

i verste tilfelle, og Merge-Sort når grensen. Det betyr
ikke at Merge-Sort alltid er det beste valget i praksis — Quicksort har
mindre konstanter og trenger ikke hjelpeplass — men på eksamen er det den

asymptotiske garantien som teller.

Begrepsbank

Begrepsbanken er flashcard- og repetisjonsstoff — den gjentar det du nettopp
har lest. Hopp trygt over ved førstegangslesing; tidsanslaget for kapitlet
gjelder kjernestoffet.

`Insertion-Sort`

\Theta(n)

`Merge`

\Theta(r-p+1)

`Merge-Sort`

\Theta(n\lg n)

`Partition`

\Theta(r-p+1)

`Quicksort`

\Theta(n\lg n)

`Randomized-Quicksort`

\Theta(n\lg n)

Løkkeinvariant

en påstand om tilstanden som gjelder rett før hver runde i en løkke, og som brukes til å vise at algoritmen er riktig. Har tre ledd: initialisering, vedlikehold og terminering. For Insertion-Sort : rett før runde j er A[1..j-1] sortert og inneholder de samme elementene som fra start.

På stedet (*in-place*)

O(1)

Stabil sortering

en sortering er stabil når to elementer med lik nøkkel beholder sin innbyrdes rekkefølge fra input til output. Insertion-Sort og Merge-Sort er stabile; Quicksort og Heapsort er det ikke. Egenskapen er avgjørende når du sorterer etter én nøkkel om gangen, slik Radix-Sort gjør. Se kap. 2.2 .

Splitt og hersk

T(n) = aT(n/b) + f(n)

Beslutningstre for sortering

n!

\Omega(n\lg n)

-grensen

\Omega(n\lg n)

Sammenligningsbasert sortering

\Omega(n\lg n)

Pivot

\Theta(n^2)

Verste tilfelle

n

Forventet kjøretid

\Theta(n\lg n)

Beste tilfelle

n

Rekurrensen

T(n) = 2T(n/2) + \Theta(n)

n/2

Rekurrensen

T(n) = T(n-1) + \Theta(n)

\Theta(n^2)

Vaktpost i `Merge`

et hjelpeelement større enn alle virkelige elementer, lagt bakerst i begge hjelpearrayene. Det gjør at flettingen slipper å teste om en av bunkene er tom i hver runde — bunken med vaktposten taper alltid sammenligningen. Ren forenkling av koden. Kjøretiden blir den samme uten den.

Sjanger E — kjøretidskunnskap

\Theta

Sjanger C — håndkjøring

oppgavetypen der du utfører en navngitt algoritme steg for steg på papir og oppgir sluttilstanden. Svarformen er kun sluttilstanden, i det formatet oppgaven ber om. Ingen ekstra uttelling for å forklare algoritmen. Drillen ligger i kap. 2.4 .

Sjanger F — «stemmer dette?»

oppgavetypen der du får en påstand og skal ta stilling til den. Svarformen er ja eller nei først, deretter én presis setning som begrunner. Et motbevis er en fullgod begrunnelse når svaret er nei — én konkret input der påstanden svikter, holder.

Repetisjonsoppgaver

Dette kapitlet er skrevet av Anthropics toppmodeller (Claude Opus og Claude Fable) og er foreløpig ikke manuelt gjennomgått — kvalitetskontrollen gjøres av uavhengige KI-agenter, og innmeldte feil rettes fortløpende. Funnet en feil? Meld fra, så retter vi den. Les mer om hvordan innholdet lages.

Skolesaga er en uavhengig læringsressurs og er ikke tilknyttet eller godkjent av Norges teknisk-naturvitenskapelige universitet. Dette er ikke offisielt studiemateriell. Les mer.

2.1 Sammenligningsbaserte sorteringer

Forkunnskaper

Insertion-Sort og løkkeinvarianten (~12 min)

Merge-Sort og rekurrensen bak den (~14 min)

Quicksort og pivotens rolle (~13 min)

Randomized-Quicksort (~6 min)

Den nedre grensen for sammenligningssortering (~10 min)

Kjøretidene samlet

Begrepsbank

`Insertion-Sort` og løkkeinvarianten (~12 min)

`Merge-Sort` og rekurrensen bak den (~14 min)

`Quicksort` og pivotens rolle (~13 min)

`Randomized-Quicksort` (~6 min)