2.3 Lineær sortering — bucket, counting og radix

Når du kan sortere i lineær tid — og den faste fellen at bucket/counting/radix krever et kjent, begrenset verdiområde.

45 min

7 oppgaver

Lineær sorteringbucketcountingradix

Din fremgang i kapitlet

0 / 7 oppgaver

Kapitlets plass i kurset

Bygger på

2.2Effektive sorteringer og nedre grense

Brukes videre i

2.4DRILL — Sorteringsegenskaper, invarianter og valg

Dette kapitlet handler like mye om når du ikke kan bruke de lineære
sorteringene som om hvordan de virker.

Sjanger D — sorteringsegenskaper og valg har vært på alle sju settene
(100 %), og de to punktene som går igjen er: «kjent, lite verdiområde $\Rightarrow$ lineær
sortering er mulig» og «bucket, counting og radix kan ikke brukes når alt vi
vet er at elementene er sammenlignbare». Det siste er felle #5 i bokas
feilregister — lineær sortering foreslått uten at forutsetningen om et kjent,
begrenset verdiområde er oppfylt — og den er den dyreste feilen i hele Del 2 av
boka, fordi den ser ut som et smart svar og er et ugyldig svar.

Du blir ikke bedt om å implementere counting sort fra bunnen på eksamen. Du blir
bedt om å velge riktig og å oppgi forutsetningen. Én setning om
verdiområdet er ofte forskjellen mellom full og halv uttelling.

Prioritet: høyeste. Dette er den siste biten av Del 2-tabellen, og den er den
mest misforståtte.

Slik er kapitlet lagt opp (45 min): tre løkker med tidsanslag.

Forkunnskaper

- kap. 2.2 — nedre grensen $\Omega(n \log n)$ for
sammenligningsbaserte sorteringer. Hele dette kapitlet handler om algoritmene
som slipper unna den, og hvorfor de får lov.
- kap. 2.1 — stabilitet, som counting sort og radix sort
er helt avhengige av.
- kap. 1.2 — løkketelling, som gir kjøretidene direkte.

Notasjons- og pseudokodeliste

Løkke 1 — counting sort: å telle i stedet for å sammenligne (ca. 16 min)

Tenk deg at du skal stille 800 elever på rekke etter hvilket klassetrinn de går
på — 1 til 10. Du ville ikke sammenlignet dem to og to. Du ville ropt opp
trinnene i rekkefølge, og latt hvert trinn stille seg der det hører hjemme.

Det er hele ideen. Du bruker ikke sammenligninger, du bruker verdien selv som
en adresse. Og fordi du aldri sammenligner, gjelder ikke nedre grensen fra
kap. 2.2.

Prisen står i eksempelet: du måtte vite på forhånd at trinnene var 1 til 10. Uten
den kunnskapen finnes det ingen rekker å stille seg i. Counting sort krever et
kjent, begrenset verdiområde, og det er nettopp forutsetningen sensor ser etter
i besvarelsen din.

Counting sort

n

📜Pseudokode-kontrakt: `CountingSort`

Antagelser om representasjon. A er et array med

n

elementer indeksert fra
0. Hvert element har en heltallsnøkkel i det kjente området

[0, k]

. Vi kan
opprette nye arrayer.

Prebetingelse: alle nøkler ligger i $[0, k]$ , og $k$ er kjent på forhånd.
Postbetingelse: returverdien er et nytt array med de samme elementene, sortert
stigende på nøkkel, og elementer med lik nøkkel står i samme innbyrdes rekkefølge
som i A.

Procedure CountingSort(A, k)
  Input:  array A med n elementer med heltallsnoekler i [0, k]
  Output: et nytt sortert array, stabilt sortert paa noekkel
  C = nytt array med k+1 plasser, alle satt til 0
  for i = 0 to A.length-1:
      C[A[i]] = C[A[i]] + 1

  for v = 1 to k:
      C[v] = C[v] + C[v-1]

  ut = nytt array med A.length plasser
  for i = A.length-1 down to 0:
      C[A[i]] = C[A[i]] - 1
      ut[C[A[i]]] = A[i]
  return ut

Grunnideen i én setning: etter den kumulative summeringen forteller C[v]
hvor mange elementer som har nøkkel høyst $v$ , og det tallet er nøyaktig én mer
enn den siste indeksen verdien $v$ skal ha i resultatet.

Stabiliteten ligger i ett ord: down to. Den siste løkka går bakfra
gjennom A. Da får det siste elementet med en gitt nøkkel den siste ledige
plassen, det nest siste får plassen foran, og innbyrdes rekkefølge bevares. Snur
du løkka, mister du stabiliteten — og dermed også muligheten til å bruke counting
sort som byggekloss i radix sort.

Kjøretid: første løkke $O(n)$ , andre løkke $O(k)$ , tredje løkke $O(n)$ .
Sumregelen gir $O(n + k)$ .

✏️Eksempel 1: Counting sort steg for steg

Sortér A = [4, 1, 3, 4, 0, 2, 1] med counting sort. Verdiområdet er kjent:
alle nøkler ligger i $[0, 4]$ , altså $k = 4$ . Vis telleregisteret, den kumulative
summen og utplasseringen.

Steg 1 — tell forekomstene. C[v] er antall elementer med verdi

v

$v$	0	1	2	3	4
`C[v]`	1	2	1	1	2

Summen er 7, som er antall elementer. Det er en fin kontroll.
Steg 2 — gjør tellingen kumulativ. Nå er P[v] antall elementer med verdi

høyst $v$ :

$v$	0	1	2	3	4
`P[v]`	1	3	4	5	7

Les det slik: det finnes tre elementer med verdi høyst 1, så de to 1-tallene må

havne på indeks 1 og 2.
Steg 3 — plassér ut, bakfra.

Steg	Element $x$	`P[x]` før	Plasseres på indeks	`ut` etter steget
1	1	3	2	`[_, _, 1, _, _, _, _]`
2	2	4	3	`[_, _, 1, 2, _, _, _]`
3	0	1	0	`[0, _, 1, 2, _, _, _]`
4	4	7	6	`[0, _, 1, 2, _, _, 4]`
5	3	5	4	`[0, _, 1, 2, 3, _, 4]`
6	1	2	1	`[0, 1, 1, 2, 3, _, 4]`
7	4	6	5	`[0, 1, 1, 2, 3, 4, 4]`

Sluttilstand: [0, 1, 1, 2, 3, 4, 4].
Se på steg 1 og 6. Begge plasserer et 1-tall. Steg 1 tar det siste

1-tallet i inputen og gir det den bakerste av de to plassene. Det er hele

mekanismen bak stabiliteten, og den er usynlig så lenge du sorterer rene tall —
den betyr noe først når hvert element bærer med seg mer enn nøkkelen.
Kjøretiden, etterregnet. Tellingen: 7 steg. Kumuleringen: 4 steg.
Utplasseringen: 7 steg. Til sammen 18 grunnsteg, altså $n + k + n$ med $n = 7$ og
$k+1 = 5$ — nøyaktig $O(n + k)$ .

📝Oppgave 1

(Innstegsoppgave, sjanger D — sorteringsvalg, altså at du velger algoritme ut fra
en oppgitt begrensning.) Et array inneholder $n$ heltall, og alle ligger mellom 0
og 5.

a) Bygg telleregisteret C for A = [2, 5, 3, 2, 5, 1].
b) Hvilken indeks får det første 2-tallet i det sorterte resultatet?
c) Er counting sort in-place?

📝Oppgave 2

Sjanger D

Du skal sortere $n$ personer etter alder. Alderen er et helt tall
mellom 0 og 120.

a) Hvilken sortering gir lavest kjøretid, og hva er den?
b) Ville svaret endret seg hvis nøklene i stedet var vilkårlige desimaltall?
c) Ville svaret endret seg hvis $n = 20$ ?

Løkke 2 — radix sort: ett siffer om gangen (ca. 14 min)

— naturlig pausepunkt —

Counting sort blir ubrukelig når verdiområdet er stort. Postnumre går fra 0000 til
9999 — det er ti tusen mulige verdier, og skal du sortere femti postnumre, er
telleregisteret to hundre ganger større enn dataene.

Radix sort løser det ved å sortere ett siffer om gangen. Hvert siffer har
bare ti mulige verdier, så hvert pass er en counting sort med $k = 9$ . Fire pass
senere er hele tallet sortert.

Rekkefølgen er det som overrasker: du sorterer på minst signifikante siffer
først. Og det virker bare fordi hvert pass er stabilt — den regelen fra
kap. 2.1 om at den siste sorteringen styrer
hovedrekkefølgen, er hele maskineriet her.

Radix sort

d

📜Pseudokode-kontrakt: `RadixSort`

Antagelser om representasjon. A er et array med

n

ikke-negative heltall,
alle med høyst

d

siffer i base 10. d er kjent på forhånd.

Prebetingelse: alle nøkler er ikke-negative heltall med høyst $d$ siffer.
Postbetingelse: A er sortert stigende.

Procedure RadixSort(A, d)
  Input:  array A med n ikke-negative heltall, hvert med hoeyst d siffer
  Output: A sortert stigende
  for s = 0 to d-1:
      sorter A stabilt paa siffer nummer s, regnet fra hoeyre
      (bruk CountingSort med k = 9 paa sifferverdien)
  return A

Grunnideen i én setning: etter passet på siffer $s$ er arrayet sortert på de
$s+1$ minst signifikante sifrene, fordi det nye passet ordner på det nye sifferet
og stabiliteten bevarer rekkefølgen fra alle de forrige.

Hvorfor minst signifikante siffer først? Fordi den siste sorteringen
styrer hovedrekkefølgen. Sorterer du på hundrerne til slutt, er hundrerne
hovednøkkelen — og innen hver hundrergruppe står tallene fortsatt sortert på
tierne og enerne fra de tidligere passene. Sorterer du motsatt vei, ødelegger det
siste passet alt arbeidet fra det forrige.

Kjøretid: $d$ pass, hvert et counting-pass på $O(n + k)$ med $k = 9$ . Totalt
$O(d(n + k))$ . Er $d$ og $k$ konstanter, er det $O(n)$ .

✏️Eksempel 2: Radix sort, tre pass

Sortér A = [329, 457, 657, 839, 436, 720] med radix sort. Alle tallene har tre
siffer, så $d = 3$ . Vis bøttene og rekkefølgen etter hvert pass.

Pass 1 — sorterer på enerne:

Bøtte	Innhold (i rekkefølgen de kom)
0	720
6	436
7	457, 657
9	329, 839

Rekkefølge etter passet: [720, 436, 457, 657, 329, 839]
Pass 2 — sorterer på tierne:

Bøtte	Innhold (i rekkefølgen de kom)
2	720, 329
3	436, 839
5	457, 657

Rekkefølge etter passet: [720, 329, 436, 839, 457, 657]
Pass 3 — sorterer på hundrerne:

Bøtte	Innhold (i rekkefølgen de kom)
3	329
4	436, 457
6	657
7	720
8	839

Rekkefølge etter passet: [329, 436, 457, 657, 720, 839]

Sluttilstand: [329, 436, 457, 657, 720, 839].
Se på bøtte 2 i pass 2: der ligger 720 foran 329, og begge har tieren 2.
Rekkefølgen mellom dem ble ikke bestemt i dette passet — den ble arvet fra pass 1,
der 720 (ener 0) kom før 329 (ener 9). Det er nettopp dette som gjør at
algoritmen virker: rekkefølgen fra forrige pass overlever inne i hver bøtte,

fordi passet er stabilt.

Prøv å ødelegge den. Hadde pass 2 vært ustabilt og lagt 329 foran 720 i

bøtte 2, ville arbeidet fra pass 1 vært tapt — og siden pass 3 bare ser på
hundrerne, ville 720 og 329 fortsatt kommet i den ødelagte rekkefølgen inne i
hver hundrergruppe. Stabilitet er ikke en fin egenskap her; det er en betingelse.
Kjøretiden, etterregnet. Tre pass, hvert på $O(n + 10)$ med $n = 6$ . Totalt
$3 \cdot 16 = 48$ grunnsteg i størrelsesorden — altså $O(d(n + k))$ med $d = 3$
og $k = 9$ .

📝Oppgave 3

Sjanger D

Sortér A = [53, 89, 15, 47, 32] med radix sort. Alle tall har to
siffer.

a) Vis rekkefølgen etter pass 1.
b) Vis rekkefølgen etter pass 2.
c) Hva er kjøretiden uttrykt ved $n$ , $d$ og $k$ ?

Løkke 3 — bucket sort, og den avgjørende begrensningen (ca. 15 min)

Bucket sort er den tredje varianten, og den er den løseste av dem. Ideen: hvis
du vet at verdiene ligger jevnt fordelt i et kjent intervall, del intervallet i
$m$ like store bøtter, kast hvert element i sin bøtte, sortér hver bøtte for seg,
og skjøt bøttene sammen i rekkefølge.

Er fordelingen jevn, får hver bøtte omtrent $n/m$ elementer, og med $m \approx n$
er hver bøtte så liten at sorteringen inne i den er nesten gratis. Da blir totalen
$O(n)$ forventet.

Er fordelingen skjev — alle elementene i én bøtte — degenererer det til å sortere
hele arrayet med den indre sorteringen, altså $O(n^2)$ med innsettingssortering.
Derfor står det «forventet» og ikke «verste» i tabellen.

Bucket sort

n

✏️Eksempel 3: Bucket sort på verdier i $[0, 1)$

Sortér A = [0.42, 0.17, 0.81, 0.35, 0.68, 0.11] med bucket sort og fem bøtter.
Verdiene er kjent å ligge i intervallet $[0, 1)$ .

Bøtte nummer for en verdi $x$ er $\lfloor x \cdot 5 \rfloor$ .

Bøtte	Intervall	Innhold
0	$[0{,}0,\ 0{,}2)$	0,17 og 0,11
1	$[0{,}2,\ 0{,}4)$	0,35
2	$[0{,}4,\ 0{,}6)$	0,42
3	$[0{,}6,\ 0{,}8)$	0,68
4	$[0{,}8,\ 1{,}0)$	0,81

Sortér innholdet i hver bøtte — her er det bare bøtte 0 som har mer enn ett
element, og innsettingssortering på to elementer er én sammenligning. Skjøt så
bøttene sammen i rekkefølge:
Sluttilstand: [0.11, 0.17, 0.35, 0.42, 0.68, 0.81].
Hva som gjorde dette lineært: fordelingen var jevn, så ingen bøtte fikk mer
enn to elementer. Den totale kostnaden ble å regne ut fem bøttenumre, gjøre én

sammenligning, og skjøte sammen — altså $O(n)$ .
Hva som ville ødelagt det: hadde alle seks verdiene ligget mellom 0,80 og
0,85, ville alle havnet i bøtte 4, og hele arbeidet ville falt på

innsettingssorteringen inne i den ene bøtta. Da er vi tilbake på $O(n^2)$ .

Og hva som ville gjort algoritmen ugyldig: hvis du ikke visste at verdiene lå
i $[0, 1)$ . Uten det intervallet finnes det ingen måte å regne ut bøttenummeret
på.

Typiske feil

Den første er felle #5 i bokas feilregister, og den er den dyreste i hele
Del 2.

- Å foreslå bucket, counting eller radix når alt du vet er at elementene er
sammenlignbare. De tre omgår $\Omega(n \log n)$ nettopp fordi de ikke
sammenligner — de bruker verdien som adresse. Det forutsetter at du vet noe om
verdiene: heltall i et kjent område, et fast antall siffer, eller et kjent
intervall. Sier oppgaven bare «elementene kan sammenlignes», er svaret
$O(n \log n)$ , og et lineært svar er feil, ikke bare uheldig.
- Å glemme heltallskravet i counting sort. Vilkårlige desimaltall kan ikke
brukes som indeks i et telleregister.
- Å oppgi counting sort som $O(n)$ uten å nevne $k$ . Kjøretiden er $O(n + k)$ .
Med $n = 1000$ og $k = 10^9$ er den langt tregere enn $O(n \log n)$ . Skriv
$O(n + k)$ og legg til at den er lineær når $k = O(n)$ .
- Å sortere fra mest signifikante siffer i radix sort. Da ødelegger hvert
pass arbeidet fra det forrige. Minst signifikante siffer først, og hvert pass
må være stabilt.
- Å blande «stabil» med «sortert riktig». Alle disse tre gir korrekt sortert
resultat. Stabilitet handler bare om rekkefølgen mellom like nøkler.

Og den gjennomgående: å bruke $n$ og $k$ uten å definere dem. Dette er felle
#10 — å oppgi kjøretid uten å si hva problemstørrelsen er. Én setning:
« $n$ er antall elementer, $k$ er størrelsen på verdiområdet.»

📝Oppgave 4

Sjanger D, eksamensnivå

For hver situasjon: kan du bruke en lineær sortering?
Hvis ja, hvilken og hva blir kjøretiden. Hvis nei, hvorfor ikke.

a) $n$ elementer der du bare vet at de kan sammenlignes med hverandre.
b) $n$ produkter som skal sorteres etter én av 12 kategorier.
c) $n$ postnumre, som alle har fire siffer.
d) $n$ målinger som er kjent å ligge jevnt fordelt mellom 0 og 100.

📝Oppgave 5

Sjanger D

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

a) Counting sort er raskere enn flettesortering på ethvert array.
b) Radix sort krever at hvert enkeltpass er stabilt.
c) Bucket sort har $O(n)$ i verste tilfelle.
d) De tre lineære sorteringene motsier nedre grensen $\Omega(n \log n)$ .

Et sideblikk: gnome sort

Eksamen har brukt et lite grep som er verdt å kjenne igjen: du får en ukjent
sorteringsalgoritme i pseudokode og skal si noe om egenskapene dens. Du forventes
ikke å ha sett den før — du forventes å gjenkjenne slektskapet.

Gnome sort er skoleeksempelet. Den går gjennom arrayet med én peker: står
naboparet riktig, går den ett skritt fram; står det feil, bytter den og går ett
skritt tilbake.

Procedure GnomeSort(A)
  Input:  array A med n sammenlignbare elementer, indeksert fra 0
  Output: A sortert stigende, sortert paa stedet
  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

Slektskapet er med innsettingssortering: begge skyver ett element bakover til det
finner plassen sin. Forskjellen er at gnome sort bruker bytter i stedet for
forskyvninger, og derfor gjør flere sammenligninger. Egenskapene arves: $O(n^2)$
verste, $O(n)$ beste på et ferdigsortert array, stabil (den bytter bare når
det foran er strengt større) og in-place.

Framgangsmåten når du møter en ukjent algoritme er alltid den samme: se på hva den
flytter og hvor langt. Korte nabobytter betyr stabil; lange hopp betyr
ustabil. Ett nytt array betyr ikke in-place.

✏️Eksempel 4: Gnome sort håndkjørt

Håndkjør GnomeSort på A = [4, 2, 5, 1] og tell steg, sammenligninger og
bytter.

Steg	`i` før	Handling	Tilstand etter
1	0	`i = 0`, gå ett fram	`[4, 2, 5, 1]`
2	1	bytt `A[0]` og `A[1]`, gå ett tilbake	`[2, 4, 5, 1]`
3	0	`i = 0`, gå ett fram	`[2, 4, 5, 1]`
4	1	`A[0] <= A[1]`, gå ett fram	`[2, 4, 5, 1]`
5	2	`A[1] <= A[2]`, gå ett fram	`[2, 4, 5, 1]`
6	3	bytt `A[2]` og `A[3]`, gå ett tilbake	`[2, 4, 1, 5]`
7	2	bytt `A[1]` og `A[2]`, gå ett tilbake	`[2, 1, 4, 5]`
8	1	bytt `A[0]` og `A[1]`, gå ett tilbake	`[1, 2, 4, 5]`
9	0	`i = 0`, gå ett fram	`[1, 2, 4, 5]`
10	1	`A[0] <= A[1]`, gå ett fram	`[1, 2, 4, 5]`
11	2	`A[1] <= A[2]`, gå ett fram	`[1, 2, 4, 5]`
12	3	`A[2] <= A[3]`, gå ett fram	`[1, 2, 4, 5]`

Sluttilstand: [1, 2, 4, 5]. 12 steg, 9 sammenligninger, 4 bytter.
Se på steg 6 til 8: 1-tallet vandrer fra indeks 3 til indeks 0, ett nabobytte
om gangen. Det er nøyaktig det innsettingssortering gjør med forskyvninger, bare
med en peker som går fram og tilbake i stedet for to nøstede løkker.
Egenskapene, lest av tabellen: algoritmen bytter bare naboer, og bare når det
foran er strengt større — altså stabil. Den bruker én indeksvariabel og ingen
nye arrayer — altså in-place. Verste tilfelle er

O(n^2)

, fordi hvert element
i verste fall må vandre hele veien.
Merk sammenligningstellingen. Innsettingssortering brukte 5 sammenligninger på
det tilsvarende arrayet i kap. 2.1; gnome sort bruker 9 her,
fordi hvert skritt tilbake koster en ny sammenligning når pekeren går fram igjen.
Samme

O

-klasse, høyere konstant.

📝Oppgave 6

Sjanger D, krevende

En kollega har skrevet dette forslaget til en Del
2-besvarelse:

«Vi skal sortere $n$ elementer som bare er kjent å være sammenlignbare. Jeg
velger radix sort fordi den er $O(n)$ og dermed står øverst i poengtrappen. Den
er også in-place, så minnebruken er $O(1)$ .»

a) Hvilke tre feil inneholder forslaget?
b) Skriv en korrekt besvarelse med algoritme, forutsetning og kjøretid.
c) Under hvilken tilleggsopplysning hadde radix sort vært riktig?

📝Oppgave 7

Sjanger D, krevende

Du skal sortere $n$ ansatte etter to nøkler: først
avdeling (12 mulige), og innen hver avdeling etter ansiennitetsår (et heltall
mellom 0 og 40).

a) Skisser en løsning som bruker counting sort, og oppgi rekkefølgen på
sorteringene.
b) Hva er samlet kjøretid?
c) Hvorfor ville løsningen brutt sammen hvis counting sort ikke var stabil?

Begrepsbank

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

Lineær sortering

\Omega(n \log n)

Kjent, begrenset verdiområde

Forutsetningen alle tre lineære sorteringene hviler på: du må vite på forhånd hvilke verdier nøklene kan ha, og området må være lite nok til at det kan adresseres. Sier oppgaven bare at elementene «kan sammenlignes», er forutsetningen ikke oppfylt, og et lineært svar er feil. Dette er felle #5 i bokas feilregister.

Telleregisteret C

v

Kumulativ sum i counting sort

v

Bakfra-løkka i counting sort

Utplasseringen går fra siste til første element i inputen. Det er dette ene valget som gjør counting sort stabil . Går løkka forfra i stedet, snus rekkefølgen mellom like nøkler — og da kan ikke counting sort brukes som byggekloss i radix sort. Detaljen er liten og konsekvensen er stor.

Counting sorts kjøretid

O(n + k)

Radix sorts pass-rekkefølge

Minst signifikante siffer først, mest signifikante sist . Grunnen er at den siste sorteringen styrer hovedrekkefølgen. Sorterer du motsatt vei, ødelegger hvert pass arbeidet fra det forrige, og resultatet blir feil.

Stabilitet som betingelse i radix sort

Hvert enkeltpass i radix sort må være stabilt. Det er ikke en ønsket egenskap, men en betingelse for at algoritmen skal virke i det hele tatt. Er ett pass ustabilt, mister arrayet rekkefølgen fra sifrene under, og de senere passene kan ikke gjenopprette den.

Radix sorts kjøretid

O(d(n + k))

Bucket sorts doble forutsetning

O(n^2)

Bucket sorts kjøretid

O(n)

Gnome sort

O(n^2)

Å gjenkjenne en ukjent sortering

\Rightarrow

Nedre grensens rekkevidde

\Omega(n \log n)

Valgregelen for sortering

O(n + k)

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.