2.2 Lineær sortering og stabilitet

`Counting-Sort`, `Radix-Sort`, `Bucket-Sort` — når lineær sortering er mulig, og hva stabilitet betyr og krever.

45 min

7 oppgaver

Lineær sorteringstabilitet

Din fremgang i kapitlet

0 / 7 oppgaver

Kapitlets plass i kurset

Bygger på

2.1Sammenligningsbaserte sorteringer

Sortering er registrert i alle de 17 settene i grunnlaget (100 %), og
spørsmålet «når kan du sortere i lineær tid?» er en av de faste variantene.
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.

To sjangre henter fra dette kapitlet, og de skrives ut i klarspråk her:

- Sjanger D — definisjon med egne ord, altså at du skriver én presis
setning med hovedpoenget først. «Definér stabil sortering» er den hyppigste
definisjonsoppgaven i sorteringsdelen.
- Sjanger E — kjøretidskunnskap, altså at du oppgir kjøretiden til en
navngitt algoritme i det strammeste uttrykket som er riktig. Her må
betingelsen med: Counting-Sort er $\Theta(n+k)$ , og det er bare lineært
når $k = O(n)$ .

Høyeste prioritet — dette må sitte. Eksamen er hjelpemiddelfri, og både
definisjonen av stabilitet og de tre kjøretidene er ren gjenkalling.

Det som skiller dette kapitlet fra det forrige: algoritmene her
sammenligner ikke elementer med hverandre. De bruker nøkkelverdien direkte som
en indeks i en tabell. Derfor er de ikke bundet av $\Omega(n\lg n)$ -grensen —
og derfor stiller de til gjengjeld krav til hvordan nøklene ser ut.

Slik er kapitlet lagt opp (45 min):

Innhold	Tid
Stabilitet, og `Counting-Sort`	ca. 16 min
`Radix-Sort` og hvorfor stabilitet er et krav	ca. 13 min
`Bucket-Sort`	ca. 8 min
Hvorfor grensen ikke er brutt	ca. 8 min

Forkunnskaper

- kap. 2.1 — sammenligningsbaserte sorteringer. Fra det
kapitlet: Merge-Sort er $\Theta(n\lg n)$ og stabil, Quicksort er
$\Theta(n\lg n)$ forventet og ustabil, og ingen sortering som bare
sammenligner elementpar kan komme under $\Omega(n\lg n)$ i verste tilfelle.
Det siste er poenget dette kapitlet spiller mot.
- kap. 1.1 — de asymptotiske symbolene. Du trenger
$\Theta$ og $O$ , og at $O(n)$ brukt om en parameter (som $k$ ) betyr «vokser
ikke raskere enn $n$ ».

Vil du se sortering konkret i kode først:
Sortering: boblesortering, .sort() og gitt sort_list.

Notasjons- og pseudokodeliste

Stabilitet, og `Counting-Sort` (~16 min)

På et postterminal kommer pakkene inn på et bånd, hver med et rutenummer fra 0
til 40. Skal du legge dem i rutenummerrekkefølge, er det tåpelig å sammenligne
pakker to og to. Du vet jo hvor mange ruter det finnes. Du kan telle hvor mange
pakker som skal til hver rute, og dermed regne ut nøyaktig hvilke plasser i
rekka hver rute skal ha.

Det er Counting-Sort. Den sammenligner aldri to elementer med hverandre — den
bruker nøkkelen som indeks i en telletabell. Prisen er at nøklene må være
heltall i et kjent, ikke altfor stort område.

Men først et begrep som hele resten av kapitlet hviler på.

Stabil sortering

En sortering er stabil når to elementer med lik nøkkel beholder sin innbyrdes rekkefølge fra input til output. Ligger to pakker med rutenummer 12 på båndet i rekkefølgen «først den fra Tromsø, så den fra Bodø», skal de ligge i den samme rekkefølgen etterpå. Egenskapen er bare interessant når elementene bærer med seg mer enn nøkkelen — en pakke er ikke bare et rutenummer. Og den er avgjørende når du sorterer etter én nøkkel om gangen, slik Radix-Sort gjør.

📜Pseudokode-kontrakt: `Counting-Sort`

Antagelser om representasjon. Arrayet er A[1..n], indeks fra 1. Hver
nøkkel A[j] er et heltall i området

[0..k]

, og

k

er kjent på
forhånd. Outputen skrives til et eget array B[1..n]; sorteringen er ikke
på stedet.

Prebetingelse: alle nøkler er heltall i $[0..k]$ .
Postbetingelse: B[1..n] inneholder de samme elementene i stigende
rekkefølge, og like nøkler står i samme innbyrdes rekkefølge som i A.

Counting-Sort(A, B, k)
  Input:  array A[1..n] med heltallsnoekler i [0..k]
  Output: B[1..n] sortert stigende, stabilt
  la C[0..k] vaere et nytt array
  for i = 0 to k
      C[i] = 0
  for j = 1 to A.length
      C[A[j]] = C[A[j]] + 1
  for i = 1 to k
      C[i] = C[i] + C[i-1]
  for j = A.length downto 1
      B[C[A[j]]] = A[j]
      C[A[j]] = C[A[j]] - 1
  Kjoeretid: Theta(n + k)

Grunnideen i én setning: etter oppsummeringen forteller C[i] hvor mange
elementer som har nøkkel høyst $i$ — og det er nøyaktig den siste ledige
plassen i B for nøkkelen $i$ .

Hvorfor den siste løkka teller nedover. Går du fra n ned til 1, blir
det siste elementet med en gitt nøkkel plassert sist blant sine like.
Snur du løkka, sorterer algoritmen fortsatt riktig, men stabiliteten
forsvinner — og da kan den ikke brukes inne i Radix-Sort.

Kjøretid: $\Theta(k)$ til å nullstille C, $\Theta(n)$ til tellingen,
$\Theta(k)$ til oppsummeringen og $\Theta(n)$ til plasseringen, altså
$\Theta(n+k)$ . Det er lineært bare når $k = O(n)$ . Med nøkler opp til
$k = n^2$ er algoritmen $\Theta(n^2)$ , og da er Merge-Sort langt bedre.

✏️Eksempel 1: `Counting-Sort` med merkede like nøkler

Fem pakker har rutenumrene A = 2, 1, 2, 3, 1 i denne rekkefølgen. For å
kunne se hva som skjer med like nøkler, merker vi dem: 2a, 1b, 2c, 3d, 1e.
Bokstaven er bare en etikett som følger elementet; sorteringen ser bare tallet.
Her er $n = 5$ og $k = 3$ .

Kjør Counting-Sort og oppgi telletabellen C etter tellingen, C etter
oppsummeringen, og det ferdige B.

Telletabellen C[0..3] etter tellingen: 0, 2, 2, 1

Ingen pakker til rute 0, to til rute 1, to til rute 2, én til rute 3.

C[0..3] etter oppsummeringen: 0, 2, 4, 5

Nå leses tabellen som «antall elementer med nøkkel høyst $i$ ». C[2] = 4
betyr at fire elementer har nøkkel 2 eller lavere — altså er plass 4 den siste
ledige plassen for en toer.

Plasseringen, bakfra:

Steg	`j`	Element	Plass i `B`	`C` etter steget	`B` etter steget
1	5	`1e`	2	`0, 1, 4, 5`	`_, 1, _, _, _`
2	4	`3d`	5	`0, 1, 4, 4`	`_, 1, _, _, 3`
3	3	`2c`	4	`0, 1, 3, 4`	`_, 1, _, 2, 3`
4	2	`1b`	1	`0, 0, 3, 4`	`1, 1, _, 2, 3`
5	1	`2a`	3	`0, 0, 2, 4`	`1, 1, 2, 2, 3`

Sluttilstanden — det du ville levert på eksamen:
B = 1, 1, 2, 2, 3, og med merkelappene:
1b, 1e, 2a, 2c, 3d.
Se på de to toerne. I input lå 2a før 2c. I output ligger 2a fortsatt før
2c — fordi løkka gikk bakfra, ble 2c plassert først, på den siste ledige
toerplassen. Det er stabilitet, konkret.

Merk hva oppgaven ba om: de tre tabellene. Ba den bare om C etter

oppsummeringen, skulle du oppgitt den ene raden og ikke mer.

📝Oppgave 1

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

Definér stabil sortering, og gi et eksempel på en situasjon der egenskapen
har betydning.

📝Oppgave 2

Eksamensnivå, sjanger C

Et array A = 4, 1, 3, 4, 0, 2, 3, 4 skal sorteres med Counting-Sort med
$k = 4$ .

a) Oppgi telletabellen C[0..4] etter tellingen.
b) Oppgi C[0..4] etter oppsummeringen.
c) Oppgi det ferdige B.

`Radix-Sort` og hvorfor stabilitet er et krav (~13 min)

Counting-Sort er ubrukelig på store nøkler: skal du sortere sekssifrede
ordrenumre, er $k = 999\,999$ , og telletabellen blir større enn hele arkivet.

Radix-Sort løser det ved å ta ett siffer om gangen. Nøkkelen har $d$ siffer,
hvert siffer ligger i et lite område, og hvert siffer sorteres for seg — med en
stabil delsortering, typisk Counting-Sort.

Det overraskende er rekkefølgen: du starter med det minst signifikante
sifferet.

📜Pseudokode-kontrakt: `Radix-Sort`

Antagelser om representasjon. Arrayet er A[1..n], indeks fra 1. Hver
nøkkel har nøyaktig

d

siffer, der siffer 1 er det minst signifikante.
Sifrene ligger i et lite område

[0..k]

— for desimaltall er

k = 9

Prebetingelse: delsorteringen som brukes per siffer, må være stabil.
Postbetingelse: A[1..n] er sortert stigende etter hele nøkkelen.

Radix-Sort(A, d)
  Input:  array A[1..n] der hver noekkel har d siffer
  Output: A sortert stigende etter hele noekkelen
  for i = 1 to d
      sorter A stabilt paa siffer i
  Kjoeretid: Theta(d(n + k))

Invarianten i én setning: etter runde i er arrayet sortert etter de i
minst signifikante sifrene under ett.

Hvorfor stabiliteten er et krav og ikke en bonus. Anta at invarianten
holder etter runde i, og at vi nå sorterer på siffer i+1. To elementer med
forskjellig siffer i+1 havner riktig av seg selv. To elementer med
samme siffer i+1 må avgjøres av de foregående sifrene — altså av
rekkefølgen de allerede har. Er delsorteringen ustabil, kastes den
rekkefølgen, og hele arbeidet fra de tidligere rundene går tapt.

Kjøretid: $d$ runder à én Counting-Sort med sifferområde $[0..k]$ , altså
$\Theta(d(n+k))$ . Med faste $d$ og $k = O(n)$ er dette $\Theta(n)$ .

✏️Eksempel 2: `Radix-Sort` siffer for siffer

Sju tresifrede lagernumre skal sorteres: `A = 482, 175, 439, 175, 908, 261,
493`. Her er $n = 7$ , $d = 3$ og sifferområdet er $[0..9]$ , altså $k = 9$ .

Kjør Radix-Sort og oppgi arrayet etter hver runde.

Runde	Sorterer på	Array etter runden
1	enerne (siffer 1)	`261, 482, 493, 175, 175, 908, 439`
2	tierne (siffer 2)	`908, 439, 261, 175, 175, 482, 493`
3	hundrerne (siffer 3)	`175, 175, 261, 439, 482, 493, 908`

Sluttilstanden: 175, 175, 261, 439, 482, 493, 908.
Følg de to like numrene 175 for å se stabiliteten arbeide: de har identiske
siffer hele veien og bytter derfor aldri innbyrdes plass. Følg heller 482 og
493. Etter runde 1 ligger 493 før 482 (3 er mindre enn 2? nei — 482 slutter på

2 og 493 på 3, så 482 kommer først). Etter runde 2 avgjør tierne: 8 mot 9, og

482 blir liggende først. Etter runde 3 er hundrerne like, 4 mot 4 — og da er
det stabiliteten som bevarer resultatet fra runde 2.
Det siste er hele poenget: i den avgjørende runden gjør delsorteringen
ingenting med disse to, og likevel er de riktig ordnet. Hadde delsorteringen
vært ustabil, kunne den snudd dem.
Kjøretid her: $\Theta(d(n+k)) = \Theta(3 \cdot (7+10))$ , altså konstant

arbeid per element per siffer.

📝Oppgave 3

Eksamensnivå, sjanger F

En student foreslår å bruke Quicksort som delsortering inne i Radix-Sort,
«siden den er raskere i praksis enn Counting-Sort».

Vil Radix-Sort da sortere riktig? Svar ja eller nei, og begrunn.

📝Oppgave 4

Eksamensnivå, sjanger E

Du skal sortere $n$ nøkler som hver har $d$ siffer i tallsystem med grunntall
$k$ .

a) Oppgi kjøretiden til Radix-Sort og til Merge-Sort på denne
inputen.
b) Finn en betingelse på $d$ og $k$ som gjør Radix-Sort asymptotisk
raskest, og forklar hva den betyr i praksis.

`Bucket-Sort` (~8 min)

Den tredje lineære sorteringen stiller en helt annen type krav: ikke til
nøklenes form, men til deres fordeling.

Ideen er å dele verdiområdet i $n$ like store intervaller — bøtter — legge hvert
element i sin bøtte, sortere hver bøtte for seg med Insertion-Sort, og
skjøte bøttene sammen i rekkefølge.

`Bucket-Sort`

n

📝Oppgave 5

Eksamensnivå, sjanger F

Ta stilling til hver av påstandene:

a) Bucket-Sort er $\Theta(n)$ i verste tilfelle.
b) Counting-Sort krever at nøklene er heltall.
c) Radix-Sort kan bruke Counting-Sort som delsortering.

Hvorfor grensen ikke er brutt (~8 min)

Et rimelig spørsmål på dette punktet: kap. 2.1 beviste
at ingen sortering kan komme under $\Omega(n\lg n)$ . Nå har vi tre som er
lineære. Er beviset galt?

Nei — og det er verdt å ha svaret klart, fordi spørsmålet stilles direkte på
eksamen.

Hvorfor lineær sortering ikke bryter grensen

\Omega(n\lg n)

✏️Eksempel 3: Hvilken sortering velger du?

Fire oppdrag. For hvert av dem: hvilken sortering fra Del 2 velger du, og
hvilken kjøretid får du?

a) 10 millioner eksamensresultater, hver et heltall fra 0 til 100.
b) 500 flyttallsmålinger fra en sensor, jevnt fordelt i $[0, 1)$ .
c) 1 million navn, sortert alfabetisk, der lik nøkkel må beholde
rekkefølgen.
d) 200 000 vilkårlige heltall uten kjent øvre grense, og du må garantere
kjøretiden.

a) Counting-Sort med

k = 100

. Her er

k

konstant og langt mindre enn

n

, så

\Theta(n+k) = \Theta(n)

. Ti millioner sammenligningsbaserte
operasjoner à

\lg n \approx 23

er sløsing når du kjenner området.

b) Bucket-Sort. Jevn fordeling er nettopp forutsetningen, og forventet
kjøretid er $\Theta(n)$ . Merk «forventet»: garantien er $\Theta(n^2)$ .

c) Merge-Sort. Den er stabil og $\Theta(n\lg n)$ garantert. Radix-Sort
på strenger er også mulig, men krever lik lengde eller polstring, og
oppgaven gir ingen grunn til å tro at $d$ er liten.

d) Merge-Sort eller Heapsort, begge $\Theta(n\lg n)$ garantert.
Ikke Quicksort: den gir bare en forventning. Ikke Counting-Sort: uten
kjent øvre grense på nøklene finnes ingen $k$ .

Svarformen på eksamen er algoritmenavnet, kjøretiden og betingelsen som
gjør valget gyldig — én linje per deloppgave. Ikke en gjennomgang av hvordan
algoritmen virker.

📝Oppgave 6

Eksamensnivå, sjanger F

En kandidat skriver: «Counting-Sort er $\Theta(n)$ , og er derfor alltid
raskere enn Merge-Sort.»

Er utsagnet riktig? Svar ja eller nei, og begrunn.

📝Oppgave 7

Eksamensnivå, sjanger H

Et bibliotek har $n$ utlån registrert med to felter: dato (et heltall fra 1 til
365) og filialnummer (et heltall fra 1 til 20). Utlånene skal sorteres etter
filial, og innenfor hver filial etter dato.

Beskriv en algoritme som bruker $\Theta(n)$ tid.

Typiske feil

De to første koster hele oppgaven.

- Å oppgi Counting-Sort som $\Theta(n)$ uten betingelsen. Dette er felle
#9 — feil kjøretidsfakta. Riktig er $\Theta(n+k)$ , og lineær bare når
$k = O(n)$ . Betingelsen er en del av svaret.
- Å tro at Radix-Sort virker med en ustabil delsortering. Stabiliteten
er ikke en bonus, den er forutsetningen for at arbeidet fra de foregående
sifferrundene overlever.
- Å sortere sifrene fra det mest signifikante og nedover. Den varianten
finnes, men den er en annen algoritme med en annen struktur.
Radix-Sort slik den er definert her, går fra minst signifikante siffer.
- Å blande stabilitet med «sorterer riktig». En ustabil sortering sorterer
helt riktig — den gir bare ingen garanti om rekkefølgen mellom like nøkler.
- Å tro at $\Omega(n\lg n)$ binder disse algoritmene. Grensen gjelder bare
sammenligningsbaserte sorteringer. Blir du spurt om hvorfor det ikke er en
selvmotsigelse, er svaret at algoritmene her aldri sammenligner to elementer
med hverandre.
- Å oppgi Bucket-Sort som $\Theta(n)$ garantert. Den er $\Theta(n)$
forventet, under antagelsen om jevn fordeling. Verste tilfelle er
$\Theta(n^2)$ .

Og den gjennomgående: å oppgi mer enn det oppgaven ber om. Ber en oppgave
om telletabellen etter oppsummeringen, er det den ene raden som er svaret —
ikke hele kjøringen.

Kjøretidene samlet

Dette er kapitlets puggeflate. Eksamen er hjelpemiddelfri, så tabellen må ligge
i hodet — og betingelsen i høyre kolonne hører med til svaret.

Algoritme	Kjøretid	Stabil?	På stedet?	Krav
`Counting-Sort`	$\Theta(n+k)$	ja	nei	heltallsnøkler i $[0..k]$ ; lineær bare når $k = O(n)$
`Radix-Sort`	$\Theta(d(n+k))$	ja	nei	$d$ siffer i området $[0..k]$ ; krever stabil delsortering
`Bucket-Sort`	$\Theta(n)$ forventet, $\Theta(n^2)$ verste	ja	nei	tilnærmet jevn fordeling over verdiområdet
`Insertion-Sort`	$\Theta(n)$ beste, $\Theta(n^2)$ verste	ja	ja	ingen — brukes som delsortering i bøttene
`Merge-Sort`	$\Theta(n\lg n)$	ja	nei	ingen — sammenligningsbasert, derfor bundet av grensen
`Quicksort`	$\Theta(n\lg n)$ forventet	nei	ja	ingen; kan ikke brukes som delsortering i `Radix-Sort`

Én presisering som er verdt å ta med seg. Alle de tre lineære sorteringene
er stabile, og alle tre trenger hjelpeplass. Det er ingen tilfeldighet: de
plasserer elementene direkte på beregnede plasser i et outputarray, og en slik
plassering er både lett å gjøre stabil og umulig å gjøre på stedet.

Begrepsbank

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

`Counting-Sort`

[0..k]

`Radix-Sort`

d

`Bucket-Sort`

n

Stabilitet

like nøkler beholder sin innbyrdes rekkefølge fra input til output. Stabile: Insertion-Sort, Merge-Sort, Counting-Sort, Radix-Sort, Bucket-Sort . Ustabile: Quicksort, Heapsort . Egenskapen er en forutsetning, ikke en bekvemmelighet, når du sorterer etter én nøkkel om gangen.

Telletabellen `C`

i

Den kumulative oppsummeringen

i

Hvorfor siste løkke går bakfra

plasseringsløkka i Counting-Sort teller fra n ned til 1 . Da blir det siste elementet med en gitt nøkkel plassert på den siste av plassene som hører til den nøkkelen — og rekkefølgen mellom like nøkler blir bevart. Snus løkka, sorterer algoritmen fortsatt riktig, men den mister stabiliteten og kan ikke lenger brukes i Radix-Sort .

Betingelsen

k = O(n)

k

Siffer og grunntall i `Radix-Sort`

d

Minst signifikante siffer først

i

Ikke-sammenligningsbasert sortering

\Omega(n\lg n)

Hvorfor

\Omega(n\lg n)

ikke gjelder her

k+1

Outputarrayet `B`

\Theta(n)

Nøkkel og satellittdata

nøkkelen er verdien det sorteres etter; satellittdataene er alt annet elementet bærer med seg. En pakke har rutenummeret som nøkkel og avsender, vekt og innhold som satellittdata. Stabilitet er bare synlig når satellittdata finnes — to like tall er ikke til å skille fra hverandre.

Sjanger D — definisjon med egne ord

oppgavetypen der du skal forklare et begrep presist og kort. Svarformen er én til to setninger med hovedpoenget først; eksempler og presiseringer kommer etter. Delvis uttelling belønner hovedpoenget, så begynn med det som faktisk definerer begrepet.

Sjanger E — kjøretidskunnskap

\Theta(n+k)

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 — én input der påstanden svikter.

Delsortering

sorteringen Radix-Sort kaller én gang per siffer, og sorteringen Bucket-Sort kjører inne i hver bøtte. I Radix-Sort må den være stabil og bør være lineær — derfor Counting-Sort . I Bucket-Sort brukes Insertion-Sort, fordi bøttene forventes å være små. Valget av delsortering er en del av algoritmen, ikke en detalj.

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.2 Lineær sortering og stabilitet

Forkunnskaper

Stabilitet, og Counting-Sort (~16 min)

Radix-Sort og hvorfor stabilitet er et krav (~13 min)

Bucket-Sort (~8 min)

Hvorfor grensen ikke er brutt (~8 min)

Kjøretidene samlet

Begrepsbank

Stabilitet, og `Counting-Sort` (~16 min)

`Radix-Sort` og hvorfor stabilitet er et krav (~13 min)

`Bucket-Sort` (~8 min)