2.4 DRILL — Sorteringsegenskaper, invarianter og valg

Full drill på sjanger D: invarianter etter *i* iterasjoner, stabilitet/in-place, kjøretider, og valg av sortering ut fra en oppgitt begrensning.

80 min

12 oppgaver

DRILLSorteringsegenskaperinvariantervalg

Din fremgang i kapitlet

0 / 12 oppgaver

Kapitlets plass i kurset

Bygger på

2.3Lineær sortering — bucket, counting og radix

Brukes videre i

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

Dette er drillkapitlet for sjanger D — sorteringsegenskaper og valg, altså
oppgavene der du krysser av sant/usant om en sortering eller velger algoritme ut
fra en oppgitt begrensning. Sjangeren har vært på alle sju settene (100 %).

Alt stoffet er fra kap. 2.1, kap. 2.2
og kap. 2.3. Her øver du på hastigheten og sikkerheten.
Sjanger D ligger i Del 1, den auto-rettede delen, der
antigjettings-skaleringen gjør at usikre svar er verdt null. En kandidat som
må tenke seg om i tjue sekunder per påstand, rekker ikke Del 2 — og en som gjetter
på halvparten, får ingenting for dem.

Målet med kapitlet er derfor todelt: at kjøretidstabellen og de tre invariantene
kommer uten opphold, og at valg-oppgavene alltid får med forutsetningen
som gjorde valget lovlig.

Prioritet: høyeste.

Slik er kapitlet lagt opp (80 min): løsningsoppskriften og et gjennomarbeidet
case først (ca. 20 min), så tolv oppgaver i tre bolker à ca. 20 min. Bolkene er
uavhengige — ta gjerne én bolk per kveld. Etter hver bolk står en boks som sier
hva oppgavene testet.

Forkunnskaper

Hele Del 2:

- kap. 2.1 — invariantene etter $i$ iterasjoner,
stabilitet og in-place.
- kap. 2.2 — flettesortering, heapsort, kvikksortering og
nedre grensen.
- kap. 2.3 — counting, radix og bucket, og forutsetningen
om verdiområdet.

Og fra Del 1: kap. 1.2 om løkketelling, som er det du
bruker når du skal lese kjøretiden ut av en ukjent sortering.

Notasjons- og pseudokodeliste

📜Løsningsoppskriften for sjanger D

Sjanger D kommer i to former, og de har hver sin oppskrift. Første steg er alltid
å se hvilken form du har.

Form 1 — egenskapsspørsmål («er dette sant?», «hva står på plass etter $i$
runder?»). Her henter du et faktum, og hastigheten kommer av at faktumet er pugget.

1. Identifisér algoritmen og egenskapen. Er det invariant, stabilitet,
in-place, eller kjøretid det spørres om?
2. Les hvilket tilfelle, hvis det er kjøretid: beste, forventet eller verste.
Dette ene ordet skiller riktig fra galt i halvparten av påstandene.
3. Hent faktumet fra tabellen. Ikke resonner deg fram — resonnering tar tid og
inviterer til feil.
4. Sjekk om påstanden er en av de faste fellene: invariantene byttet om,
«kvikksortering $O(n \log n)$ verste», «flettesortering in-place», «heapsort
stabil», «build-heap $O(n \log n)$ ».

Form 2 — valg-spørsmål («hvilken sortering passer her, og hva koster den?»).

1. Hva vet du om verdiene? Heltall i et kjent, lite område $\Rightarrow$ counting eller
radix, $O(n + k)$ eller $O(d(n+k))$ . Kjent intervall og jevn fordeling $\Rightarrow$ bucket,
$O(n)$ forventet. Bare «sammenlignbare» $\Rightarrow$ ingen lineær sortering er lovlig.
2. Kreves stabilitet? Da faller kvikksortering, heapsort og utvalgssortering
bort.
3. Er det minne- eller garantikrav? Ikke in-place $\Rightarrow$ flettesortering faller
bort. Krav om garantert $O(n \log n)$ $\Rightarrow$ kvikksortering faller bort.
4. Oppgi kjøretiden som matcher valget, med $n$ (og $k$ eller $d$ ) definert.
5. Skriv ut forutsetningen som gjorde et lineært valg lovlig. Det er dette
delmomentet som oftest glemmes, og det er poenggivende for seg selv.

Puggeflaten begge formene henter fra:

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

✏️Gjennomarbeidet eksamenscase med sensorkommentarer

(Eksamensnivå, sjanger D.) Et sett har denne oppgaven, verdt 6 poeng:

a) (2 p) Arrayet [7, 2, 9, 4, 1, 6] sorteres. Hva er tilstanden etter 2
fullførte iterasjoner av den ytre løkka, med henholdsvis boblesortering,
utvalgssortering og innsettingssortering?

b) (2 p) Marker sant eller usant: (i) heapsort er stabil; (ii) counting sort
er $O(n)$ uansett verdiområde; (iii) innsettingssortering plasserer de $i$ første
elementene endelig etter $i$ runder.

c) (2 p) Du skal sortere $n$ ordrer etter leveringsdag (heltall 1 til 365),
og ordrer fra samme dag må beholde rekkefølgen de kom inn i. Hvilken sortering
velger du? Oppgi kjøretiden.

a) Håndkjøringene.

Boblesortering:

Etter iterasjon	Tilstand	Låst
1	`[2, 7, 4, 1, 6, 9]`	`[9]` til høyre
2	`[2, 4, 1, 6, 7, 9]`	`[7, 9]` til høyre

Utvalgssortering:

Etter iterasjon	Tilstand	Låst
1	`[1, 2, 9, 4, 7, 6]`	`[1]` til venstre
2	`[1, 2, 9, 4, 7, 6]`	`[1, 2]` til venstre

Innsettingssortering:

Etter iterasjon	Tilstand	Sortert prefiks
1	`[2, 7, 9, 4, 1, 6]`	`[2, 7]`, ikke endelig
2	`[2, 7, 9, 4, 1, 6]`	`[2, 7, 9]`, ikke endelig

Sensornotat, a) — 2 poeng. Typisk fordeling er 0,5 p per riktig tilstand og
0,5 p for å oppgi hvilke elementer som er låst. Legg merke til at
utvalgssortering ikke gjorde noe bytte i runde 2 — 2-tallet lå allerede riktig.
Det er et vanlig sted å skrive feil, fordi tilstanden ser uendret ut.
Delvis riktig gir delvis uttelling: har du to av tre algoritmer riktig, får
du to av tre delpoeng. Aldri la et felt stå tomt.

b) Sant/usant.
(i) Usant. Heapsort er in-place, men ikke stabil — uttrekket flytter
elementer over lang avstand.

(ii) Usant. Counting sort er $O(n + k)$ . Er verdiområdet stort, dominerer
$k$ , og algoritmen blir tregere enn $O(n \log n)$ .
(iii) Usant. Innsettingssortering sorterer de $i+1$ første innbyrdes,
ikke endelig.

Sensornotat, b) — 2 poeng. Tre påstander, alle usanne, og alle tre er faste
distraktorer. Merk at «alle usant» er et mulig fasitmønster på en enkelt
deloppgave, selv om en hel sant/usant-blokk alltid blander. Under
antigjettings-skaleringen får den som gjetter på alle tre i snitt 1,5 riktige —
og etter skaleringen er det null. Det finnes ingen delvis kredit for å ha
«nesten» rett her.

c) Valget.

Dette er form 2 i oppskriften. Hva vet vi om verdiene? Leveringsdagen er et
heltall i et kjent område, $[1, 365]$ , altså $k = 365$ . Kreves stabilitet? Ja

— ordrer fra samme dag skal beholde rekkefølgen.
Svar: counting sort, som er både lineær og stabil.
Kjøretid: $O(n + k)$ med $n$ = antall ordrer og $k = 365$ . Siden $k$ er en
konstant, er dette $O(n)$ .
Forutsetningen, skrevet ut: leveringsdagen er et heltall i et kjent, begrenset
område, så counting sort er lovlig. Stabiliteten er ivaretatt fordi

utplasseringsløkka går bakfra.

Sensornotat, c) — 2 poeng. Poengfordelingen er typisk 1 p for riktig
algoritme og 1 p for riktig kjøretid med forutsetningen oppgitt. En
besvarelse som skriver «counting sort, $O(n)$ » og stopper der, får som regel
halv uttelling. En besvarelse som velger flettesortering og skriver
$O(n \log n)$ , er korrekt og får uttelling — men ikke full, fordi
poengtrappen gir mest for lavest kjøretid. En besvarelse som velger
kvikksortering, mister også stabilitetspoenget.

Samlet: de 6 poengene henger på tre ting — at tabellen sitter, at du leser
hvilket tilfelle det spørres om, og at du skriver ut forutsetningen. Ingen av

delene krever regning.

Bolk 1 — invarianter og håndkjøring (ca. 20 min)

Fem oppgaver på det som gir raskest poeng: hva står hvor etter $i$ runder.

📝Oppgave 1

Eksamensnivå, sjanger D

[3, 8, 1, 5] sorteres med hver av de tre
kvadratiske algoritmene.

a) Tilstand etter 1 iterasjon med boblesortering?
b) Tilstand etter 1 iterasjon med utvalgssortering?
c) Tilstand etter 1 iterasjon med innsettingssortering?

📝Oppgave 2

Eksamensnivå, sjanger D

[7, 2, 9, 4, 1, 6] sorteres med utvalgssortering.

a) Tilstand etter 3 iterasjoner?
b) Hvor mange bytter er gjort etter 3 iterasjoner?
c) Hvor mange sammenligninger gjør den indre løkka i iterasjon 4?

📝Oppgave 3

Eksamensnivå, sjanger D

[7, 2, 9, 4, 1, 6] sorteres med innsettingssortering.

a) Tilstand etter 4 iterasjoner?
b) Er noen elementer garantert endelig plassert?
c) Hva ville tilstanden vært etter 4 iterasjoner med boblesortering?

📝Oppgave 4

Eksamensnivå, sjanger D

Et array med 30 elementer sorteres.

a) Etter 8 runder med boblesortering — hvilke indekser er garantert ferdige?
b) Etter 8 runder med utvalgssortering — hvilke indekser er garantert ferdige?
c) Etter 8 runder med innsettingssortering — hvor mange elementer er sortert
innbyrdes?
d) Hvilken av de tre har gjort færrest bytter så langt, i verste tilfelle?

📝Oppgave 5

Eksamensnivå, sjanger D

Fire deltakere står i denne rekkefølgen, med
startgruppa i parentes:

Rud(2), Lie(1), Aas(2), Bo(1)

Lista sorteres på startgruppe.

a) Hva blir resultatet med innsettingssortering?
b) Hva blir resultatet med utvalgssortering?
c) Hvilken av de to ville du valgt hvis lista på forhånd var sortert
alfabetisk og den alfabetiske rekkefølgen skulle overleve innen hver gruppe?

Bolk 1 rullerte gjennom hele invariant-repertoaret:

- Oppgave 1 testet at du kan kjøre én runde av hver av de tre — inkludert den
runden som ikke gjør noe.
- Oppgave 2 testet utvalgssorteringens byttetelling, der runden uten bytte er
fella.
- Oppgave 3 testet skillet mellom «sortert innbyrdes» og «garantert endelig».
- Oppgave 4 testet invariantene i ren form, uten å måtte kjøre noe: du skulle
svare på indekser for $n = 30$ .
- Oppgave 5 testet stabilitet demonstrert på data, ikke bare som påstand.

Klarte du 4 og 5 uten å kjøre algoritmene i hodet, sitter invariantene. Måtte du
kjøre dem, er det de to setningene i
kap. 2.1 du skal pugge: største til høyre, minste til
venstre, og innbyrdes til venstre uten garanti.

Bolk 2 — egenskaper og kjøretider (ca. 20 min)

— naturlig pausepunkt —

Fire oppgaver på tabellen. Målet er at svarene skal komme uten opphold.

📝Oppgave 6

Eksamensnivå, sjanger D

Fyll ut tabellen for alle sju sorteringene. Skriv
verste kjøretid, om algoritmen er stabil, og om den er in-place.

Algoritme	Verste	Stabil?	In-place?
Boblesortering
Utvalgssortering
Innsettingssortering
Flettesortering
Heapsort
Kvikksortering
Counting sort

📝Oppgave 7

Eksamensnivå, sjanger C…

Avgjør sant eller usant med én setnings
begrunnelse.

a) Utvalgssortering har $O(n)$ i beste tilfelle.
b) Flettesortering er $O(n \log n)$ også i verste tilfelle.
c) Kvikksortering er in-place.
d) Å bygge en heap fra et vilkårlig array er $O(n \log n)$ .
e) Radix sort krever at hvert enkeltpass er stabilt.

📝Oppgave 8

Eksamensnivå, sjanger D

Et array A med $n$ elementer er allerede sortert.
Oppgi kjøretiden for hver algoritme på nettopp denne inputen.

a) Innsettingssortering
b) Utvalgssortering
c) Flettesortering
d) Kvikksortering med siste element som pivot

📝Oppgave 9

Eksamensnivå, sjanger…

Denne pseudokoden er en sortering du ikke
har sett før.

Procedure UkjentSort(A)
  Input:  array A med n sammenlignbare elementer, indeksert fra 0
  Output: A sortert stigende
  i = 0
  while i < A.length:
      if i == 0 or A[i-1] <= A[i]:
          i = i + 1
      else:
          bytt A[i-1] og A[i]
          i = i - 1

a) Er algoritmen stabil? Begrunn.
b) Er den in-place? Begrunn.
c) Hva er verste og beste kjøretid?
d) Håndkjør den på [3, 1, 2] og tell steg.

- Oppgave 6 var tabellen selv, i eksamensform. Den kommer igjen som
matriseavkryssing (sjanger F).
- Oppgave 7 rullerte de fem hyppigste distraktorene: utvalgssorteringens
beste tilfelle, flettesorteringens garanti, kvikksorteringens minnebruk,
build-heap, og stabilitetskravet i radix.
- Oppgave 8 testet at du skiller mellom asymptotisk klasse og faktisk ytelse
på én bestemt input.
- Oppgave 9 testet framgangsmåten for en ukjent algoritme — den du
trenger når settet gir deg pseudokode uten navn.

Oppgave 9 er den formen som er vanskeligst å pugge seg gjennom, og den enkleste å
lære en metode for. Metoden er tre spørsmål: hva flyttes, hvor langt, og hvor
mange nye arrayer.

Bolk 3 — valg av sortering (ca. 20 min)

Tre oppgaver på form 2 av oppskriften. Her er forutsetningen like mye verdt som
algoritmen.

📝Oppgave 10

Eksamensnivå, sjanger D

For hver situasjon: velg sortering, oppgi kjøretiden,
og skriv ut forutsetningen som gjør valget lovlig.

a) $n$ eksamensbesvarelser som skal sorteres på karakter (A til F).
b) $n$ flyttall som bare er kjent å kunne sammenlignes.
c) $n$ ordrenumre på nøyaktig seks siffer.
d) $n$ elementer der minnet er svært knapt, men kjøretiden må være garantert
$O(n \log n)$ .

📝Oppgave 11

Eksamensnivå, sjanger…

En besvarelse lyder:

«Jeg sorterer de $n$ elementene med bucket sort, som er $O(n)$ . Deretter skanner
jeg naboparene i $O(n)$ for å finne duplikater. Totalt $O(n)$ , som er lavest
mulig og gir full uttelling i poengtrappen.»

Oppgaven sa: «Gitt et usortert array med $n$ heltall, avgjør om to av dem er
like.»

a) Hva er galt?
b) Hva er det høyeste lovlige trinnet i poengtrappen på denne oppgaven?
c) Skriv en korrekt besvarelse.

📝Oppgave 12

Eksamensnivå, sjanger…

Du skal sortere $n$ pakker på tre nøkler:
først sone (8 mulige), så vektklasse (heltall 0 til 20), og til slutt
prioritet (heltall 0 til 3). Sone er hovednøkkelen, prioritet den minst viktige.

a) Skisser en løsning med counting sort. Oppgi rekkefølgen på passene.
b) Hva er samlet kjøretid?
c) Hva ville gått galt hvis ett av passene var ustabilt?
d) Hvordan ville du løst det hvis sone var en tekststreng i stedet for et
tall?

Typiske feil — fellekatalogen for sjanger D

Samlet, i den rekkefølgen de koster mest poeng.

- Å bytte om invariantene. Boblesortering låser de $i$ største til
høyre; utvalgssortering de $i$ minste til venstre;
innsettingssortering sorterer de $i+1$ første innbyrdes, uten garanti.
- Å foreslå bucket, counting eller radix på generelle sammenlignbare
elementer. Felle #5 i bokas feilregister. Uten kjent, begrenset
verdiområde er lineær sortering ikke lovlig, og svaret er feil — ikke bare
uheldig.
- Å oppgi verste der oppgaven spør om forventet, eller motsatt. Gjelder først
og fremst kvikksortering: $O(n \log n)$ forventet, $O(n^2)$ verste.
- Å blande stabil og in-place. Kvikksortering er in-place og ustabil;
flettesortering er stabil og ikke in-place. De to egenskapene henger ikke
sammen.
- Å blande antall bytter med antall sammenligninger. Utvalgssortering har
færrest bytter (høyst $n-1$ ), men like mange sammenligninger som boblesortering.
- Å hoppe over forutsetningen i et valg-svar. «Counting sort, $O(n)$ » uten å
nevne heltall og kjent område gir som regel halv uttelling.
- Å bruke $n$ eller $k$ uten å definere dem. Felle #10 — å oppgi kjøretid
uten å si hva problemstørrelsen er. Én setning holder.

Begrepsbank

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

Sjanger D — sorteringsegenskaper og valg

Del 1-sjangeren dette kapitlet driller: sant/usant om invarianter, stabilitet, in-place og kjøretid, pluss «hvilken sortering passer denne begrensningen». Har vært på 7 av 7 sett (100 %). Ligger i den auto-rettede delen med antigjettings-skalering, så usikre svar er verdt null.

Oppskriften for egenskapsspørsmål

Fire steg: 1) identifisér algoritme og egenskap; 2) les hvilket tilfelle det spørres om; 3) hent faktumet fra tabellen; 4) sjekk om påstanden er en av de faste fellene. Steg 3 er poenget: du skal hente, ikke resonnere. Resonnering tar tid og inviterer til feil under tidspress.

Oppskriften for valg-spørsmål

Fem steg: 1) hva vet du om verdiene? 2) kreves stabilitet? 3) er det minne- eller garantikrav? 4) oppgi kjøretiden som matcher valget; 5) skriv ut forutsetningen. Steg 5 er delmomentet som oftest glemmes, og det er poenggivende for seg selv.

De fem markerte cellene i tabellen

k

Å lese egenskaper ut av ukjent pseudokode

\Rightarrow

Runden uten bytte i utvalgssortering

Utvalgssortering gjør bytte bare når minsteelementet blant de gjenværende ikke allerede lå på riktig plass. Tilstanden ser da uendret ut, men invarianten gjelder likevel. Det er et av de vanligste stedene å skrive feil i en håndkjøring, fordi det er lett å tro at man har hoppet over en runde.

Antall sammenligninger i iterasjon

i

i

Asymptotisk klasse er ikke en garanti per input

O(n)

Poengtrappen blant lovlige løsninger

O(n)

Rekkefølgen ved sortering på flere nøkler

Sortér på den minst viktige nøkkelen først og på hovednøkkelen sist, med en stabil algoritme i hvert pass. Regelen er kontraintuitiv, den er maskineriet i radix sort, og den kommer igjen hver gang en oppgave har en hovednøkkel og en andrenøkkel.

Delvis uttelling i en håndkjøring

En håndkjøringsoppgave gir poeng per riktig deltilstand. Har du to av tre algoritmer riktig, får du delpoengene for de to. Konsekvensen er praktisk: la aldri et felt stå tomt . En tilstand du er usikker på, er verdt mer enn en blank rute — på de ikke-strafferammede oppgavene er ubesvart det samme som feil.

Antigjettingens konsekvens for sjanger D

På en sant/usant-blokk skaleres poengsummen slik at ren gjetting i snitt gir null. Halvparten riktig er ikke halve poengsummen, men ingenting. Derfor er målet i dette kapitlet sikkerhet og hastighet, ikke gjenkjennelse. Men merk motsatsen: på korte svar uten strafferamme er ubesvart det samme som feil, og der lønner det seg alltid å svare.

Repetisjon — kortet du tar med til eksamen

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.