2.2 Effektive sorteringer og nedre grense

Merge, Heap og Quick sort som O(n log n)-sorteringer (Quick O(n²) verste) — hva de brukes til på Del 2 (sortér-så-skann), ikke håndkjøring.

50 min

8 oppgaver

Effektive sorteringernedre grense

Din fremgang i kapitlet

0 / 8 oppgaver

Kapitlets plass i kurset

Bygger på

2.1Sammenligningsbaserte sorteringer og invarianter

Brukes videre i

2.3Lineær sortering — bucket, counting og radix 4.4Heap og prioritetskø

De tre effektive sorteringene testes på to måter, og begge har vært på alle
sju settene (100 %).

Sjanger D — sorteringsegenskaper og valg (sant/usant om stabilitet, in-place
og kjøretid) og sjanger C — kjøretids- og teorifakta (rene faktapåstander)
plukker begge fra den samme tabellen. Det klart hyppigste enkeltpunktet er
kvikksorteringens verste tilfelle: $O(n^2)$ , ikke $O(n \log n)$ .

Den andre bruken er viktigere for karakteren. På Del 2 — der du skriver
pseudokode — er «sortér i $O(n \log n)$ og skann i $O(n)$ » en helt lovlig
strategi når ingen lineær løsning finnes. Da må du kunne si hvilken sortering du
bruker og hva den koster. Det er nettopp dette som gjør kapitlet til mer enn
puggestoff.

Du blir ikke bedt om å håndkjøre flettesortering eller kvikksortering på
eksamen — heapstrukturen håndkjøres derimot, og den bygges opp i Del 4. Her
handler det om egenskaper, kjøretid og valg.

Prioritet: høyeste. Tabellen nederst i kapitlet er ren poengvaluta på Del 1.

Slik er kapitlet lagt opp (50 min): fire løkker med tidsanslag og et
pausepunkt underveis.

Forkunnskaper

- kap. 2.1 — stabilitet, in-place og de tre invariantene.
Alle begrepene brukes videre her uten ny forklaring.
- kap. 1.2 — løkketelling. Kjøretidene under regnes ut ved
å telle nivåer og arbeid per nivå, som er den samme tellingen.
- kap. 1.1 — $O$ , $\Omega$ og forskjellen mellom verste og
forventet tilfelle.

Vil du se boblesortering kjøre som ekte kode først:
Sortering: boblesortering, .sort() og gitt sort_list.

Notasjons- og pseudokodeliste

Løkke 1 — flettesortering og nivåtellingen (ca. 14 min)

Tenk deg to bunker med søknader, hver allerede sortert på dato. Å slå dem sammen
til én sortert bunke er lett: se på det øverste arket i hver bunke, ta det
eldste, gjenta. Du går gjennom hvert ark nøyaktig én gang.

Det er hele ideen bak flettesortering (merge sort). Del arrayet i to,
sortér hver halvdel — med samme metode — og flett de to sorterte halvdelene
sammen.

Det avgjørende for kjøretiden er ikke rekursjonen i seg selv, men hvor mange
ganger et array på $n$ elementer kan halveres før bitene har ett element. Det
er $\log_2 n$ ganger. Og på hvert nivå gjør flettingen til sammen $O(n)$
arbeid, fordi hvert element passerer gjennom nøyaktig én fletting per nivå.

$\log_2 n$ nivåer, $O(n)$ arbeid per nivå. Det gir $O(n \log n)$ . Legg merke til
at dette er ren telling — vi setter ikke opp noen ligning.

Flettesortering

O(n \log n)

📜Pseudokode-kontrakt: `MergeSort` og `Merge`

Antagelser om representasjon. A er et array med

n

sammenlignbare
elementer indeksert fra 0. Vi har lov til å opprette nye arrayer.

Prebetingelse: A inneholder $n$ elementer i vilkårlig rekkefølge.
Postbetingelse: returverdien er et nytt array med de samme elementene, sortert
stigende.

Procedure MergeSort(A)
  Input:  array A med n sammenlignbare elementer, indeksert fra 0
  Output: et sortert array med de samme elementene
  if A.length <= 1:
      return A
  m = A.length / 2
  venstre = MergeSort(A[0 .. m-1])
  hoyre   = MergeSort(A[m .. A.length-1])
  return Merge(venstre, hoyre)

Flettingen er den delen som gjør arbeidet, og den er verdt å kunne skrive:

Procedure Merge(V, H)
  Input:  to sorterte arrayer V og H
  Output: ett sortert array med alle elementene fra V og H
  ut = tomt array
  i = 0
  j = 0
  while i < V.length and j < H.length:
      if V[i] <= H[j]:
          legg V[i] bakerst i ut
          i = i + 1
      else:
          legg H[j] bakerst i ut
          j = j + 1
  legg resten av V (fra i) bakerst i ut
  legg resten av H (fra j) bakerst i ut
  return ut

Grunnideen i én setning: to sorterte biter kan flettes ved å alltid ta det
minste av de to første elementene, fordi det ikke kan finnes noe mindre lenger
bak i en sortert bit.

Kjøretid: Merge går gjennom hvert element én gang, altså $O(m)$ for samlet
lengde $m$ . Splittingen gir $\log_2 n$ nivåer, og på hvert nivå flettes til
sammen $n$ elementer. Totalt $O(n \log n)$ , i alle tilfeller.

Stabiliteten ligger i ett tegn: V[i] <= H[j]. Fordi venstre vinner ved
likhet, beholder like elementer sin innbyrdes rekkefølge. Bytter du til <,
slutter flettesortering å være stabil.

✏️Eksempel 1: Flettesortering nivå for nivå

Kjør MergeSort på A = [8, 3, 5, 1, 9, 2]. Vis splittefasen og flettefasen,
og tell antall sammenligninger.

Splittefasen — hvert nivå halverer bitene:

Nivå	Biter
0	`[8, 3, 5, 1, 9, 2]`
1	`[8, 3, 5]` `[1, 9, 2]`
2	`[8]` `[3, 5]` `[1]` `[9, 2]`
3	`[3]` `[5]` `[9]` `[2]`

Flettefasen — nedenfra og opp:

Nivå	Venstre	Høyre	Flettet	Sammenligninger
2	`[3]`	`[5]`	`[3, 5]`	1
2	`[9]`	`[2]`	`[2, 9]`	1
1	`[8]`	`[3, 5]`	`[3, 5, 8]`	2
1	`[1]`	`[2, 9]`	`[1, 2, 9]`	1
0	`[3, 5, 8]`	`[1, 2, 9]`	`[1, 2, 3, 5, 8, 9]`	5

Sluttilstand: [1, 2, 3, 5, 8, 9]. I alt 10 sammenligninger.
Sammenlign med kap. 2.1: de kvadratiske sorteringene
brukte 12 til 15 sammenligninger på nøyaktig det samme arrayet. Med seks

elementer er forskjellen liten. Med en million elementer er den ca. 20 millioner

mot ca. 500 milliarder.
Kontrollregning av nivåtellingen. Arrayet har 6 elementer, og $\log_2 6$
ligger mellom 2 og 3 — vi fikk tre flettenivåer, som stemmer. På hvert nivå ble
det flettet til sammen 6 elementer eller færre. Så $3 \times 6 = 18$ er et tak,
og vi brukte 10 sammenligninger. Det er nettopp $O(n \log n)$ .
Merk hjelpearrayet. Merge bygger et nytt ut-array. Det er derfor
flettesortering ikke er in-place, og det er et fast sant/usant-punkt.

📝Oppgave 1

(Innstegsoppgave, sjanger C — kjøretids- og teorifakta, altså rene
sant/usant-påstander om algoritmer.) Avgjør sant eller usant.

a) Flettesortering er $O(n \log n)$ også i verste tilfelle.
b) Flettesortering er in-place.
c) Flettesortering er stabil.

Løkke 2 — heapsort, kort og presist (ca. 8 min)

Heapsort får en kort omtale her og full behandling i Del 4, der selve
heap-strukturen bygges og håndkjøres. Det du trenger for Del 1 nå, er de tre
linjene i tabellen.

Ideen: gjør arrayet om til en heap — en struktur der du alltid kan plukke ut
det minste elementet raskt — og plukk deretter ut elementene ett for ett.
Uttrekket koster $O(\log n)$ og gjøres $n$ ganger, altså $O(n \log n)$ .

Ett tall her er lett å bomme på, og det er et fast sant/usant-punkt: å bygge
heapen fra et vilkårlig array koster $O(n)$ , ikke $O(n \log n)$ . Det er selve
uttrekksfasen som koster logaritmisk per element.

Heapsort

O(n \log n)

Å bygge en heap er lineært

O(n)

Løkke 3 — kvikksortering og de to kjøretidene (ca. 14 min)

— naturlig pausepunkt —

Kvikksortering (quicksort) angriper problemet fra motsatt kant av
flettesortering. Der flettesortering deler blindt på midten og gjør arbeidet i
flettingen, gjør kvikksortering alt arbeidet i delingen — og trenger ingen
fletting i det hele tatt.

Metoden heter partisjonering: velg ett element som pivot, og still om
arrayet slik at alt som er mindre enn pivoten havner til venstre for den, og alt
som er større havner til høyre. Da står pivoten på sin endelige plass, og du kan
sortere de to sidene hver for seg.

Her ligger både styrken og svakheten. Deler pivoten omtrent på midten hver gang,
får du $\log_2 n$ nivåer og $O(n \log n)$ . Havner pivoten ytterst hver gang,
skreller du av bare ett element per nivå — og da får du $n$ nivåer og $O(n^2)$ .

Kvikksortering

O(n \log n)

Pivot

O(n^2)

📜Pseudokode-kontrakt: `Partition`

Antagelser om representasjon. A er et array indeksert fra 0. Vi
partisjonerer delen fra indeks lav til og med høy, og bruker A[høy] som
pivot. Sorteringen skjer på stedet.

Prebetingelse: lav <= høy. Postbetingelse: pivoten står på indeksen som
returneres; alt til venstre for den er mindre, alt til høyre er større eller lik.

Procedure Partition(A, lav, hoy)
  Input:  array A, og indeksene lav og hoy som avgrenser biten
  Output: indeksen der pivoten A[hoy] havnet, med alt mindre til venstre
  pivot = A[hoy]
  i = lav
  for j = lav to hoy-1:
      if A[j] < pivot:
          bytt A[i] og A[j]
          i = i + 1
  bytt A[i] og A[hoy]
  return i

Selve sorteringen er da tre linjer:

Procedure QuickSort(A, lav, hoy)
  Input:  array A og indeksene lav og hoy
  Output: A[lav..hoy] sortert stigende, sortert på stedet
  if lav < hoy:
      p = Partition(A, lav, hoy)
      QuickSort(A, lav, p-1)
      QuickSort(A, p+1, hoy)

Invarianten i én setning: rett før hver runde av for-løkka er alt i
A[lav..i-1] mindre enn pivoten, og alt i A[i..j-1] er større eller lik.

Kjøretid: én partisjonering av en bit med $m$ elementer koster $m-1$
sammenligninger, altså $O(m)$ . Deler pivoten omtrent på midten, blir det
$\log_2 n$ nivåer med $O(n)$ arbeid hver — $O(n \log n)$ . Havner pivoten ytterst
hver gang, blir det $n-1$ nivåer med $n-1, n-2, \ldots$ sammenligninger, altså
$\displaystyle \frac{n(n-1)}{2}$ — $O(n^2)$ .

✏️Eksempel 2: Én partisjonering, steg for steg

Partisjonér A = [7, 2, 9, 4, 1, 6] med A[høy] = 6 som pivot. Vis hvert steg
av for-løkka, og oppgi hvor pivoten havner.

`j`	`A[j]` før	`A[j] < 6`?	Handling	Array etter	`i` etter
0	7	nei	la stå	`[7, 2, 9, 4, 1, 6]`	0
1	2	ja	bytt plass 0 og 1	`[2, 7, 9, 4, 1, 6]`	1
2	9	nei	la stå	`[2, 7, 9, 4, 1, 6]`	1
3	4	ja	bytt plass 1 og 3	`[2, 4, 9, 7, 1, 6]`	2
4	1	ja	bytt plass 2 og 4	`[2, 4, 1, 7, 9, 6]`	3
—	—	—	bytt pivoten inn på plass 3	`[2, 4, 1, 6, 9, 7]`	3

Sluttilstand: [2, 4, 1, 6, 9, 7]. Pivoten 6 står nå endelig på indeks 3.
Venstre del er [2, 4, 1], høyre del er [9, 7]. Partisjoneringen brukte 5
sammenligninger, altså

n-1

.
Legg merke til to ting.
For det første: venstre og høyre del er ikke sortert. Partisjonering
garanterer bare at alle til venstre er mindre enn pivoten. Sorteringen skjer når
QuickSort kalles rekursivt på hver side.

For det andre: pivoten 6 havnet nesten midt i arrayet, som er heldig. Delingen
ble 3 mot 2, og da får vi det gode tilfellet. Neste eksempel viser det motsatte.
Om stabiliteten. Byttet bytt A[i] og A[j] flytter et element over lang

avstand — akkurat som i utvalgssortering, og med samme konsekvens.

Kvikksortering er ustabil.

📝Oppgave 2

Sjanger D

Partisjonér A = [3, 8, 5, 2, 7] med siste element som pivot.

a) Hvilken indeks havner pivoten på?
b) Hvordan ser arrayet ut rett etter partisjoneringen?
c) Hvor mange sammenligninger brukte partisjoneringen?

✏️Eksempel 3: Verste tilfelle — hvorfor $O(n^2)$

Hvorfor blir kvikksortering med siste element som pivot $O(n^2)$ på et array som
allerede er sortert? Vis regnestykket for $n = 8$ .

Partisjonér A = [1, 2, 3, 4, 5] med A[høy] = 5 som pivot:

`j`	`A[j]` før	`A[j] < 5`?	Handling	Array etter	`i` etter
0	1	ja	bytt plass 0 og 0	`[1, 2, 3, 4, 5]`	1
1	2	ja	bytt plass 1 og 1	`[1, 2, 3, 4, 5]`	2
2	3	ja	bytt plass 2 og 2	`[1, 2, 3, 4, 5]`	3
3	4	ja	bytt plass 3 og 3	`[1, 2, 3, 4, 5]`	4
—	—	—	bytt pivoten inn på plass 4	`[1, 2, 3, 4, 5]`	4

Pivoten havnet helt til høyre. Venstre del har fire elementer, høyre del er
tom. Neste kall får altså bare ett element færre, ikke halvparten.
Nivåtellingen for $n = 8$ :

Nivå	Største bit	Arbeid på nivået
0	8	7 sammenligninger
1	7	6 sammenligninger
2	6	5 sammenligninger
3	5	4 sammenligninger
4	4	3 sammenligninger
5	3	2 sammenligninger
6	2	1 sammenligning

Sju nivåer, og summen er

7+6+5+4+3+2+1 = 28

sammenligninger. Det er

\displaystyle \frac{n(n-1)}{2}

med

n = 8

— trekantsummen fra

kap. 1.2, altså $O(n^2)$ .
Sammenlign med flettesortering på samme $n$ : fire nivåer med 8 elementer

hver, altså høyst 32 elementbevegelser, men bare tre flettenivåer med reelt

arbeid. For $n = 8$ er forskjellen liten. For $n = 1\,000\,000$ er den forskjellen
mellom sekunder og dager.
Dette er kapitlets viktigste enkeltfaktum. Kvikksortering er $O(n \log n)$
forventet og $O(n^2)$ verste. Skriver du bare « $O(n \log n)$ » uten å
nevne hvilket tilfelle, er svaret ufullstendig.

📝Oppgave 3

Sjanger C og D

Avgjør sant eller usant, og begrunn hver med én setning.

a) Kvikksortering har $O(n \log n)$ i verste tilfelle.
b) Heapsort er stabil.
c) Flettesortering trenger $O(n)$ ekstra minne.
d) Å bygge en heap fra et vilkårlig array tar $O(n \log n)$ .

Løkke 4 — nedre grensen, tegnet ut (ca. 14 min)

Nå kan vi gjøre ferdig det kap. 2.1 bare skisserte: hvorfor
$O(n \log n)$ ikke bare er bra, men optimalt for en sammenligningsbasert
sortering.

Tenk på algoritmen som en person som skal gjette hvilken av rekkefølgene input
har, og som bare får stille ja/nei-spørsmål av typen «er $x$ mindre enn $y$ ?».
Hvert spørsmål deler mulighetene i to. Alle mulige spørsmålsrekker danner til
sammen et beslutningstre: en node per spørsmål, to grener ut, og ett blad per
mulig sluttrekkefølge.

Beslutningstre for sortering

n!

📜Nedre grensen:

\Omega(n \log n)

Påstand. Enhver sammenligningsbasert sortering bruker minst

\Omega(n \log n)

sammenligninger i verste tilfelle.

Bevisskissen, i fire steg — dette er den formen sensor ber om:

1. Tell mulighetene. $n$ ulike elementer kan stå i $n!$ ulike rekkefølger.
Algoritmen må kunne ende opp med hver av dem, avhengig av input.
2. Tell informasjonen. Hver sammenligning gir ett ja/nei-svar. Med $k$
sammenligninger finnes det høyst $2^k$ ulike svarsekvenser, altså høyst $2^k$
ulike blader.
3. Sett dem opp mot hverandre. For å skille alle $n!$ rekkefølger må
$2^k \ge n!$ , altså $k \ge \log_2(n!)$ .
4. Forenkl. $\log_2(n!)$ vokser som $n \log n$ . En rask måte å se det på: mer
enn halvparten av faktorene i $n!$ er større enn $n/2$ , så
$n! > (n/2)^{n/2}$ , og logaritmen av det er $\displaystyle \frac{n}{2}\log_2\frac{n}{2}$ ,
som er $\Omega(n \log n)$ .

Hva grensen gjelder. Verste tilfelle, og bare for algoritmer som kun
sammenligner. Beste tilfelle kan godt være $O(n)$ — innsettingssortering på et
ferdigsortert array bruker $n-1$ sammenligninger.

Hva grensen ikke gjelder. Algoritmer som ser på verdiene i stedet for å
sammenligne dem. Counting sort, radix sort og bucket sort i
kap. 2.3 kommer under grensen nettopp fordi de ikke er
sammenligningsbaserte. De betaler for det med en antagelse om verdiområdet.

✏️Eksempel 4: Beslutningstreet for tre elementer

Tegn ut beslutningstreet for å sortere tre ulike elementer $a$ , $b$ og $c$ , og
sjekk at høyden stemmer med formelen.

Med tre elementer finnes det $3! = 6$ mulige rekkefølger, altså seks blader.
Her er alle veiene gjennom treet, med den beste spørsmålsstrategien:

Blad	Sluttrekkefølge	Sammenligninger på veien	Antall
1	$a < b < c$	$a<b$ ? ja; $a<c$ ? ja; $b<c$ ? ja	3
2	$a < c < b$	$a<b$ ? ja; $a<c$ ? ja; $b<c$ ? nei	3
3	$c < a < b$	$a<b$ ? ja; $a<c$ ? nei	2
4	$b < a < c$	$a<b$ ? nei; $a<c$ ? ja	2
5	$b < c < a$	$a<b$ ? nei; $a<c$ ? nei; $b<c$ ? ja	3
6	$c < b < a$	$a<b$ ? nei; $a<c$ ? nei; $b<c$ ? nei	3

Seks blader, største dybde 3.
Kontroll mot formelen. Nedre grensen sier at høyden må være minst

\log_2(3!) = \log_2 6 \approx 2{,}58

, og siden antall sammenligninger er et
helt tall, minst 3. Treet vårt har høyde nøyaktig 3 — grensen er altså stram
her.
Legg merke til bladene 3 og 4. De nås med bare to sammenligninger. Nedre
grensen sier ikke at hver input krever tre sammenligninger, bare at den

verste gjør det. Det er nettopp derfor grensen gjelder verste tilfelle og ikke

beste.
Prøv formen hvis dette kommer som en Del 2-oppgave: «Det finnes $n!$ mulige
rekkefølger. Hver sammenligning gir ett bit, så $k$ sammenligninger skiller høyst
$2^k$ tilfeller. Da må $2^k \ge n!$ , altså $k \ge \log_2(n!) = \Omega(n \log n)$ .»

Tre setninger, og alle de tre momentene sensor teller er med.

📝Oppgave 4

Sjanger C, eksamensnivå

Nedre grensen sier $\Omega(n \log n)$ .

a) Hvor mange sammenligninger trenger et beslutningstre minst for å sortere
4 ulike elementer?
b) Motsier det nedre grensen at innsettingssortering bruker $n-1$
sammenligninger på et ferdigsortert array?
c) Motsier det nedre grensen at counting sort kan sortere i $O(n + k)$ ?

Kjøretidstabellen for alle sju sorteringene

Dette er bokas viktigste puggeflate for Del 1. De tre øverste er fra
kap. 2.1, de tre neste er dette kapitlet, og counting sort
kommer i kap. 2.3.

Algoritme	Beste	Verste	Forventet	Stabil?	In-place?
Boblesortering	$O(n)$ med tidlig stopp	$O(n^2)$	$O(n^2)$	ja	ja
Utvalgssortering	$O(n^2)$	$O(n^2)$	$O(n^2)$	nei	ja
Innsettingssortering	$O(n)$	$O(n^2)$	$O(n^2)$	ja	ja
Flettesortering	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	ja	nei
Heapsort	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	nei	ja
Kvikksortering	$O(n \log n)$	$O(n^2)$	$O(n \log n)$	nei	ja
Counting sort	$O(n + k)$	$O(n + k)$	$O(n + k)$	ja	nei

Tre observasjoner som dekker de fleste sant/usant-punktene:
1. Bare kvikksortering har ulikt verste og forventet tilfelle blant de tre
effektive. Det er derfor den er den hyppigste distraktoren.
2. Bare flettesortering er både $O(n \log n)$ garantert og stabil — og prisen
er at den ikke er in-place.
3. Counting sort er den eneste under $n \log n$ , og den er der bare fordi den
ikke sammenligner. Merk

k

: den er lineær i

n + k

, ikke i

n

alene.

Del 2-bruken: «sortér og skann»

Dette er grunnen til at kapitlet betyr noe utover Del 1.

På en Del 2-oppgave — der du skal skrive pseudokode og oppgi kjøretid — dukker
det stadig opp problemer av typen «finnes det to like elementer?» eller «finnes
det to elementer som summerer til $x$ ?». På et usortert array har du to
lovlige veier:

- Sortér i $O(n \log n)$ og skann i $O(n)$ . Totalt $O(n \log n)$ .
- Bruk et hash-set i $O(n)$ forventet. Se
kap. 3.2 og kap. 3.4.

Begge er riktige. Men de gir ulikt antall poeng, fordi sensorveiledningene er
eksplisitte på at lavere kjøretid er mer poenggivende — den regelen kalles
poengtrappen i denne boka. Den lineære løsningen står øverst.

To ting du ikke kan gjøre, og som begge gir trekk:

- Bruke bucket sort eller radix sort som «raskere sortering» når alt du vet er at
elementene kan sammenlignes. De krever et kjent, begrenset verdiområde — se
kap. 2.3.
- Skrive $O(n \log n)$ uten å si hvilken sortering du bruker. Kjøretiden må matche
algoritmen du faktisk oppga.

Typiske feil

Fem dokumenterte poengtap, i synkende rekkefølge etter hvor ofte de dukker opp.

- Å oppgi $O(n \log n)$ som kvikksorteringens verste tilfelle. Verste er
$O(n^2)$ ; $O(n \log n)$ er forventet. Skriv alltid hvilket tilfelle du snakker
om.
- Å tro at flettesortering er in-place. Den trenger $O(n)$ ekstra minne til
flettingen. Dette er den vanligste feilen om flettesortering.
- Å tro at heapsort er stabil. Den er in-place, men ikke stabil — de to
egenskapene forveksles fordi de nevnes sammen.
- Å påstå at BuildHeap er $O(n \log n)$ . Den er $O(n)$ . Selve
heapsorteringen er $O(n \log n)$ , og det er den blandingen som skaper feilen.
- Å bruke $n$ uten å definere det. Felle #10 i bokas feilregister — å
oppgi kjøretid eller drøfte uten å si hva problemstørrelsen er. Én setning
holder.

Og én til, som gjelder Del 2: å foreslå bucket eller radix på generelle
sammenlignbare elementer. Det er felle #5 — lineær sortering brukt uten at
forutsetningen om et kjent, begrenset verdiområde er oppfylt.

📝Oppgave 5

Sjanger D, eksamensnivå

Velg sortering for hver situasjon, og oppgi
kjøretiden.

a) 2 millioner poster som skal sorteres på dato, og rekkefølgen mellom poster
med samme dato må bevares.
b) Et innebygd system med svært lite minne, der ekstra arrayer ikke er mulig,
men kjøretiden må være garantert $O(n \log n)$ .
c) Generell sortering av tall der du bare bryr deg om forventet ytelse, og
minnebruken skal være lav.

📝Oppgave 6

Sjanger C og D

Et array på $n$ elementer er allerede sortert.

a) Hva er kjøretiden til flettesortering på det?
b) Hva er kjøretiden til kvikksortering med siste element som pivot?
c) Hva er kjøretiden til heapsort?
d) Hva sier dette om påstanden «effektive sorteringer er alltid raskere enn
kvadratiske»?

📝Oppgave 7

Sjanger D, krevende

Du får et usortert array A med $n$
heltall og skal avgjøre om det finnes to like elementer.

a) Skriv en løsning som bruker sortering. Oppgi antagelser og kjøretid.
b) En medstudent foreslår å bruke radix sort «fordi den er lineær». Hva er
problemet?
c) Hva er det høyeste trinnet i poengtrappen på denne oppgaven?

📝Oppgave 8

Sjanger C, krevende

Avgjør sant eller usant, og begrunn.

a) Hvis en sortering er $O(n \log n)$ i verste tilfelle, kan den ikke være
sammenligningsbasert.
b) Nedre grensen $\Omega(n \log n)$ gjelder også for counting sort.
c) En sammenligningsbasert sortering kan avgjøre om et array allerede er
sortert i $O(n)$ .
d) Kvikksortering kan gjøres til $O(n \log n)$ i verste tilfelle ved å velge
pivoten tilfeldig.

Begrepsbank

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

Fletting

O(m)

Nivåtelling

\log_2 n

Partisjonering

O(m)

Kvikksorteringens verste tilfelle

O(n^2)

Forventet kontra verste kjøretid

O(n \log n)

Tilfeldig pivotvalg

O(n \log n)

Flettesortering er ikke in-place

O(n)

Heapsort er in-place men ustabil

O(1)

Merge sort i verste tilfelle

O(n \log n)

Sortér-og-skann-strategien

O(n \log n)

Poengtrappen for sorteringsvalg

O(n)

Beslutningstrehøyde

n!

Rekkevidden til en nedre grense

\Omega(n \log n)

Sjanger C — kjøretids- og teorifakta

Del 1-sjangeren der du krysser av sant/usant på rene faktapåstander om kjøretider, sorteringsegenskaper, heap, hashing og P/NP. Har vært på 7 av 7 sett (100 %). Kombinert med antigjettings-skaleringen betyr det at kjøretidstabellen må sitte hjelpemiddelfritt: den som er usikker på halvparten, ender på null.

Repetisjon — kapitlet på ett kort

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 Universitetet i Oslo. Dette er ikke offisielt studiemateriell. Les mer.