2.4 DRILL — Sortering: håndkjøring, kjøretid og kombinasjon

Full drill på sjanger C (håndkjøring av `Counting-Sort`/`Partition`) og E (kjøretidsfakta + kombinasjonsspørsmål: rekkefølgen på to sorteringer).

80 min

15 oppgaver

DRILLSorteringhåndkjøringkjøretidkombinasjon

Din fremgang i kapitlet

0 / 15 oppgaver

Kapitlets plass i kurset

Bygger på

2.3Utvelgelse — Partition, Randomized-Select og Select

Brukes videre i

2.PPrøver til del 2: Sortering og utvelgelse

Sortering er registrert i alle de 17 settene i grunnlaget (100 %) — ingen
andre temaer er sikrere. 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.

Tre sjangre driller vi her, og de skrives ut i klarspråk:

- Sjanger C — håndkjøring, altså at du utfører algoritmen steg for steg på
papir og oppgir bare sluttilstanden. Counting-Sort og Partition er de to
som kommer i sorteringsdelen.
- Sjanger E — kjøretidskunnskap, altså at du oppgir kjøretiden til en
navngitt algoritme i det strammeste uttrykket som er riktig. Dette er den
billigste poengtypen i hele faget: sju algoritmer, tre tall hver, og de er
aldri annerledes.
- Kombinasjonsspørsmålet, en fast variant av sjanger E: du kjører to
sorteringer etter hverandre og skal si hvilken rekkefølge som gir billigst
total.

Høyeste prioritet — dette må sitte. Eksamen er hjelpemiddelfri, og alt i
dette kapitlet er ren gjenkalling eller ren mekanikk.

Slik er kapitlet lagt opp (80 min):

Innhold	Tid
Løsningsoppskriften	ca. 8 min
Den gjennomarbeidede eksamenscasen	ca. 14 min
Drill på `Counting-Sort`	ca. 15 min
Drill på `Partition`	ca. 15 min
Drill på kjøretidsfakta	ca. 13 min
Kombinasjonsspørsmål	ca. 15 min

— naturlig pausepunkt — etter Partition-drillen er du halvveis. Resten er
faktakunnskap og kan tas i en egen økt.

Forkunnskaper

- kap. 2.1 — Insertion-Sort, Merge-Sort,
Quicksort og Randomized-Quicksort, med kjøretider og
$\Omega(n\lg n)$ -grensen.
- kap. 2.2 — Counting-Sort, Radix-Sort,
Bucket-Sort og stabilitet.
- kap. 2.3 — Partition med siste element som pivot,
og utvelgelse.
- kap. 1.1 — de asymptotiske symbolene, og skillet
mellom $\Theta$ og $O$ .

Alle sju algoritmene er innført der. Dette kapitlet legger ikke til nytt stoff —
det gjør stoffet til en ferdighet.

Notasjons- og pseudokodeliste

📜Løsningsoppskriften for sorteringsoppgaver

Steg 1 — avgjør hvilken sjanger oppgaven er. Ber den deg utføre noe, er
det håndkjøring (C). Ber den om et tall eller et uttrykk, er det
kjøretidskunnskap (E). Ber den deg velge mellom algoritmer eller rekkefølger,
er det kombinasjonsspørsmålet.

Steg 2 ved håndkjøring: utfør algoritmen mekanisk, linje for linje,
uten å ta snarveier og uten å reparere en input som ser rar ut. Skriv ned
tilstanden etter hvert steg mens du regner — det er der delpoengene ligger hvis
du bommer til slutt.

Steg 3 ved håndkjøring: oppgi kun det etterspurte.

Oppgaven ber om	Du leverer
telletabellen etter tellingen	den ene raden `C[0..k]`
telletabellen etter oppsummeringen	den ene raden `C[0..k]`
resultatet av `Counting-Sort`	arrayet `B[1..n]`
`Partition`	arrayet etterpå og `q`, hvis begge er spurt om
én runde av `Insertion-Sort`	arrayet etter den runden, ikke hele sorteringen

Steg 4 ved kjøretid: hent faktumet fra tabellen, og les spørsmålet én gang
til for å se om det gjelder beste, verste eller forventet. Skriv

\Theta

der grensen er tett og

O

der bare øvre grense er vist. Trengs en
utregning, hold den på én linje.
Steg 5 ved kombinasjon: finn ut hvilken av de to sorteringene som er
inputfølsom, og sørg for at den kjøres på den inputen som passer den best.

Insertion-Sort er den eneste inputfølsomme i pensum: $\Theta(n)$ på sortert
input, $\Theta(n^2)$ ellers.
Steg 6: skriv svaret på én til tre linjer. Lange svar gir ingen ekstra
uttelling, og de stjeler tid fra de nitten andre oppgavene.

✏️Eksempel 1: Gjennomarbeidet eksamenscase med margnotater

Dette er et sett på tre deloppgaver av den typen som kommer sammen på arket.
Les margnotatene: de sier hva som gir uttelling ved hvert steg.

a) Arrayet A = 3, 1, 4, 1, 0, 4, 2, 3, 4 skal sorteres med
Counting-Sort med $k = 4$ . Oppgi telletabellen C etter oppsummeringen.

b) Kjør Partition(A, 1, 6) på A = 61, 27, 84, 13, 55, 42. Oppgi arrayet
etterpå og pivotens sluttindeks q.

c) En algoritme kjører først Merge-Sort på hele arrayet og deretter
Insertion-Sort på resultatet. Hva er total kjøretid?

a) Telletabellen etter tellingen er
1, 2, 1, 2, 3 — én nuller, to enere, én
toer, to treere og tre firere.

Etter oppsummeringen: C = 1, 3, 4, 6, 9

Margnotat. Oppgaven ba om tabellen etter oppsummeringen. Leverer du
tabellen etter tellingen, har du svart på et annet spørsmål — og hele
deloppgaven ryker, selv om regningen er riktig. Kontrollen: siste celle skal
være $n = 9$ .

Margnotat. Kjøringen videre — plasseringen bakfra — var ikke etterspurt,
og skal ikke med i svaret. (Til orientering blir B = 0, 1, 1, 2, 3, 3, 4, 4, 4.)

b) Pivoten er A[6] = 42.

`j`	Test	Array etter runden
1	`A[1]=61` $>$ 42	`61, 27, 84, 13, 55, 42`
2	`A[2]=27` $\le$ 42	`27, 61, 84, 13, 55, 42`
3	`A[3]=84` $>$ 42	`27, 61, 84, 13, 55, 42`
4	`A[4]=13` $\le$ 42	`27, 13, 84, 61, 55, 42`
5	`A[5]=55` $>$ 42	`27, 13, 84, 61, 55, 42`

Etter løkka står i på 3, og siste steg bytter A[4] og A[6].
Array: 27, 13, 42, 61, 55, 84, og q = 3.
Margnotat. Her ba oppgaven om begge deler. Leverer du bare arrayet, får
du typisk delvis uttelling — hovedpoenget er der, men ett ledd mangler.
Margnotat. En vanlig feil er å sortere sidene etterpå «for at det skal se
riktig ut». Ikke gjør det: Partition lover ingenting om rekkefølgen innenfor

sidene, og et sortert svar er et galt svar på denne oppgaven.

c) $\Theta(n\lg n)$ .

Margnotat. Begrunnelsen skal være én linje: Merge-Sort koster
$\Theta(n\lg n)$ , og etterpå er arrayet sortert, så Insertion-Sort treffer

sitt beste tilfelle og koster $\Theta(n)$ . Summen domineres av det første
leddet.
Margnotat. Motsatt rekkefølge er den fellen oppgaven egentlig tester: kjører

du Insertion-Sort først, kan den alene koste $\Theta(n^2)$ , og totalen blir

$\Theta(n^2)$ .
På eksamen leverer du de tre linjene under — resten er utregning:
- a) C = 1, 3, 4, 6, 9
- b) 27, 13, 42, 61, 55, 84, q = 3

- c) $\Theta(n\lg n)$

Drill: `Counting-Sort` (~15 min)

Fem oppgaver på håndkjøring. Legg merke til hvor ulikt de spør — svarformatet
skifter fra oppgave til oppgave, og det er en del av testen.

📝Oppgave 1

Eksamensnivå, sjanger C

A = 2, 0, 3, 2, 1, 3, 3 skal sorteres med Counting-Sort med

k = 3

Oppgi telletabellen C[0..3] etter tellingen.

📝Oppgave 2

Eksamensnivå, sjanger C

Samme array som i oppgave 1: A = 2, 0, 3, 2, 1, 3, 3, $k = 3$ .

Oppgi C[0..3] etter den kumulative oppsummeringen, og forklar med én
setning hva tallet i C[2] betyr.

📝Oppgave 3

Eksamensnivå, sjanger C

A = 1, 4, 1, 0, 4, 2 skal sorteres med Counting-Sort med

k = 4

Oppgi det ferdige outputarrayet B.

📝Oppgave 4

Eksamensnivå, sjanger C…

To pakker har samme rutenummer 5. I inputarrayet ligger pakke P før pakke
Q.

a) Hvor ligger de i forhold til hverandre etter Counting-Sort?
b) Ville svaret vært det samme hvis den siste løkka gikk fra 1 og oppover
til n?

📝Oppgave 5

Eksamensnivå, sjanger C

Seks lagernumre skal sorteres med Radix-Sort: `A = 271, 039, 415, 082, 260,
417`. Hvert nummer skrives med tre siffer, altså $d = 3$ .

Oppgi arrayet etter hver av de tre rundene.

Drill: `Partition` (~15 min)

Fire oppgaver. Husk at svarformatet er arrayet etterpå og q når begge er
spurt om, og at sidene ikke skal sorteres.

📝Oppgave 6

Eksamensnivå, sjanger C

Kjør Partition(A, 1, 7) på A = 38, 71, 15, 62, 29, 47, 33 med siste element
som pivot.

a) Oppgi arrayet etterpå.
b) Oppgi q.

📝Oppgave 7

Eksamensnivå, sjanger C

Kjør Partition(A, 1, 6) på A = 9, 14, 22, 31, 45, 50 — et array som
allerede er sortert.

a) Oppgi arrayet etterpå og q.
b) Hva forteller resultatet om Quicksorts kjøretid på sortert input?

📝Oppgave 8

Eksamensnivå, sjanger C

Kjør Partition(A, 1, 5) på A = 56, 41, 68, 23, 12.

Oppgi arrayet etterpå og q.

📝Oppgave 9

Eksamensnivå, sjanger…

A = 44, 17, 63, 25, 58, 31.

a) Kjør Quicksort(A, 1, 6) og oppgi arrayet etter den første
partisjoneringen.
b) Hvilke to deler blir de rekursive kallene gjort på?
c) Oppgi det ferdig sorterte arrayet.

Drill: kjøretidsfakta (~13 min)

Tre oppgaver på ren gjenkalling. Dette er de billigste poengene i faget, og de
er gratis hvis tabellen sitter.

📝Oppgave 10

Eksamensnivå, sjanger E

Oppgi beste og verste kjøretid for hver av de sju sorteringene: Insertion-Sort,
Merge-Sort, Quicksort, Randomized-Quicksort, Heapsort, Counting-Sort
og Radix-Sort. Ta med betingelsene der de finnes.

📝Oppgave 11

Eksamensnivå, sjanger E

For hvert utsagn: er kjøretiden riktig oppgitt? Rett den om nødvendig.

a) Insertion-Sort er $\Omega(n\lg n)$ i beste tilfelle.
b) Build-Max-Heap er $\Theta(n\lg n)$ .
c) Randomized-Select er $\Theta(n)$ i verste tilfelle.
d) Counting-Sort er $\Theta(n)$ .

📝Oppgave 12

Eksamensnivå, sjanger E

Du skal sortere $n$ elementer og må garantere kjøretiden — en forventning
holder ikke.

a) Hvilke av de sju sorteringene kan du bruke, og hva blir garantien?
b) Hvilke må du utelukke, og hvorfor?

Kombinasjonsspørsmål (~15 min)

Den siste varianten er en fast felle: du får to sorteringer og skal si hvilken
rekkefølge som er billigst. Nøkkelen er å finne den inputfølsomme
algoritmen.

📝Oppgave 13

Eksamensnivå, sjanger E

Du kjører først den ene algoritmen på hele arrayet, deretter den andre på
resultatet.

a) For hvilken rekkefølge av Merge-Sort og Insertion-Sort blir total
kjøretid $\Theta(n\lg n)$ ?
b) Hva blir totalen i motsatt rekkefølge?
c) Begrunn med et talleksempel.

📝Oppgave 14

Eksamensnivå, sjanger E

Du kjører først Counting-Sort på en sekundærnøkkel, deretter
Insertion-Sort på primærnøkkelen. Nøklene er heltall i $[0..k]$ med
$k = O(n)$ .

a) Blir resultatet sortert riktig etter begge nøklene?
b) Hva er total kjøretid i verste tilfelle?

📝Oppgave 15

Eksamensnivå, sjanger F

En kandidat skriver: «Vi kjører Merge-Sort og deretter Counting-Sort med
$k = n$ . Totalen blir $\Theta(n)$ , siden Counting-Sort er lineær og den siste
sorteringen bestemmer resultatet.»

Stemmer konklusjonen? Svar ja eller nei, og begrunn.

Typiske feil

De to første koster hele oppgaven.

- Å oppgi mer enn det som er spurt om. Ber oppgaven om telletabellen etter
oppsummeringen, er den ene raden hele svaret. Ber den om arrayet etter én
Insertion-Sort-runde, skal du ikke levere hele sorteringen. Dette er den
hyppigste kilden til tapte poeng i sjanger C — ikke fordi svaret er galt,
men fordi det ikke er svaret på spørsmålet.
- Å oppgi feil kjøretidsfakta. Dette er felle #9. De fire som går
igjen: Insertion-Sort beste som $\Omega(n\lg n)$ (den er $\Theta(n)$ ),
Build-Max-Heap som $\Theta(n\lg n)$ (den er $\Theta(n)$ ),
Randomized-Select verste som $\Theta(n)$ (den er $\Theta(n^2)$ ), og
Counting-Sort som $\Theta(n)$ uten betingelsen $k = O(n)$ .
- Å sortere sidene etter Partition. Rutinen lover bare hvilken side hvert
element havner på. Et «pent» svar der begge sidene er sortert, er galt.
- Å velge feil rekkefølge i kombinasjonsspørsmålet. Den inputfølsomme
sorteringen skal ha den inputen som passer den best — altså skal
Insertion-Sort kjøres sist, på et allerede sortert array.
- Å tro at bare det siste steget teller. To steg etter hverandre koster
summen av begge.
- Å reparere en input som ser rar ut. Kjører du en algoritme på en input
som ikke oppfyller den vanlige forutsetningen, skal du utføre trinnene
mekanisk og levere det du får.

Og den gjennomgående: å bruke tid på en forklaring ingen har bedt om.
Tjue oppgaver teller likt; tiden er den knappeste ressursen på arket.

Kjøretidene du kan bli spurt om i en deloppgave

Algoritme	Beste	Verste	Forventet	Stabil	På stedet	Betingelse
`Insertion-Sort`	$\Theta(n)$	$\Theta(n^2)$	$\Theta(n^2)$	ja	ja	beste på sortert input
`Merge-Sort`	$\Theta(n\lg n)$	$\Theta(n\lg n)$	$\Theta(n\lg n)$	ja	nei	—
`Quicksort`	$\Theta(n\lg n)$	$\Theta(n^2)$	$\Theta(n\lg n)$	nei	ja	verste på sortert input
`Randomized-Quicksort`	$\Theta(n\lg n)$	$\Theta(n^2)$	$\Theta(n\lg n)$	nei	ja	forventet gjelder enhver input
`Heapsort`	$\Theta(n\lg n)$	$\Theta(n\lg n)$	$\Theta(n\lg n)$	nei	ja	—
`Counting-Sort`	$\Theta(n+k)$	$\Theta(n+k)$	$\Theta(n+k)$	ja	nei	heltall i $[0..k]$ ; lineær når $k = O(n)$
`Radix-Sort`	$\Theta(d(n+k))$	$\Theta(d(n+k))$	$\Theta(d(n+k))$	ja	nei	krever stabil delsortering
`Bucket-Sort`	$\Theta(n)$	$\Theta(n^2)$	$\Theta(n)$	ja	nei	krever jevn fordeling
`Partition`	$\Theta(m)$	$\Theta(m)$	$\Theta(m)$	—	ja	$m$ = lengden på delen

Heapsort og Build-Max-Heap hører hjemme i kap. 3.1;
de står her fordi de er en del av den samme puggeflaten på eksamen.

Begrepsbank

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

Svarformat for `Counting-Sort`

n

Svarformat for `Partition`

\le

Svarformat for én sorteringsrunde

ber oppgaven om arrayet etter én bestemt runde, leverer du den ene tilstanden — ikke hele sorteringen. For Insertion-Sort betyr «runde j » at A[1..j] er ordnet og resten er urørt. Å kjøre ferdig hele sorteringen er å svare på et annet spørsmål.

Kombinasjonsregelen

\Theta(n\lg n)

Inputfølsom sortering

\Theta(n)

Felle #9 — feil kjøretidsfakta

å oppgi et kjøretidstall som gjelder et annet tilfelle enn det spørsmålet handler om. De fire som går igjen: Insertion-Sort beste, Build-Max-Heap, Randomized-Select verste, og Counting-Sort uten betingelse. Kontrollen er å lese spørsmålet én gang til og finne ordet «beste», «verste» eller «forventet».

Mekanisk håndkjøring

å utføre algoritmen nøyaktig slik pseudokoden sier, også når inputen ikke ser ut som forventet. Du reparerer ikke, forenkler ikke og hopper ikke over steg. Det er den mekaniske kjøringen oppgaven spør etter, ikke det svaret algoritmen «burde» gitt.

Delvis uttelling i sjanger C

en håndkjøring som er delvis riktig, gir delvis uttelling — derfor lønner det seg å skrive ned tilstanden etter hvert steg mens du regner. Mangler ett ledd av et sammensatt svar (for eksempel q når både array og q var spurt om), trekkes det typisk bare for det leddet. Blankt ark gir null. Et delvis svar gir noe.

Sjanger C — håndkjøring

oppgavetypen der du utfører en navngitt algoritme steg for steg og oppgir sluttilstanden. Svarformen er kun sluttilstanden, i det formatet oppgaven ber om. Den hyppigste håndkjøringen i sorteringsdelen er Counting-Sort og Partition .

Sjanger E — kjøretidskunnskap

oppgavetypen der du oppgir kjøretiden til en navngitt algoritme. Svarformen er ett uttrykk, i det strammeste som er riktig, med betingelsen der den finnes. Den billigste poengtypen i faget — hvis tabellen sitter.

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. Et konkret motbevis holder når svaret er nei.

Garantert mot forventet

en garanti gjelder for enhver kjøring; en forventning er et gjennomsnitt over algoritmens tilfeldige valg. Merge-Sort og Heapsort gir garantier; Quicksort og Randomized-Quicksort gir forventninger. Spør oppgaven om en garanti, er Quicksort feil svar — uansett hvor rask den er i praksis.

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.4 DRILL — Sortering: håndkjøring, kjøretid og kombinasjon

Forkunnskaper

Drill: Counting-Sort (~15 min)

Drill: Partition (~15 min)

Drill: kjøretidsfakta (~13 min)

Kombinasjonsspørsmål (~15 min)

Kjøretidene du kan bli spurt om i en deloppgave

Begrepsbank

Drill: `Counting-Sort` (~15 min)

Drill: `Partition` (~15 min)