2.1 Sammenligningsbaserte sorteringer og invarianter

Bubble, Selection og Insertion sort — mekanikk, kjøretider, og de invariantene etter *i* iterasjoner som sensor spør om direkte.

55 min

8 oppgaver

Sammenligningsbaserte sorteringerinvarianter

Din fremgang i kapitlet

0 / 8 oppgaver

Kapitlets plass i kurset

Bygger på

1.2Kjøretidsanalyse fra kode — løkketelling

Brukes videre i

2.2Effektive sorteringer og nedre grense 4.1Binære søketrær (BST)

Sortering er ett av de fire temaene som har vært på alle sju settene i arkivet
(100 %) — men nesten aldri slik du kanskje tror.

Du blir så godt som aldri bedt om å håndkjøre en hel sortering. Du blir bedt om
egenskapene: hvilke elementer som står trygt på plass etter et gitt antall
runder, om algoritmen er stabil, om den bruker ekstra minne, og hva kjøretiden
er i beste og verste tilfelle.

Sjanger D — sorteringsegenskaper og valg, altså at du krysser av sant/usant
om en sorteringsalgoritme eller velger riktig algoritme ut fra en oppgitt
begrensning, er sjangeren dette kapitlet trener. Den ligger i Del 1, den
auto-rettede delen av eksamen, og den er derfor underlagt
antigjettings-skaleringen: poengsummen på en sant/usant-blokk skaleres slik
at ren gjetting i snitt gir null. Halvparten riktig er ikke halve poengsummen —
det er ingenting. Fakta i dette kapitlet må sitte sikkert, ikke omtrentlig.

Prioritet: høyeste. Dette er billige, garanterte poeng, og de tre
algoritmene her er de eneste sorteringene UiO faktisk ber deg redegjøre for
detalj for detalj.

Slik er kapitlet lagt opp (55 min i alt): fire arbeidsløkker med tidsanslag,
og pausepunkter merket underveis. Du kan trygt ta løkke 1 og 2 én kveld og
løkke 3 og 4 den neste.

Forkunnskaper

- kap. 1.2 — løkketelling. Alle kjøretidene i dette
kapitlet leses rett ut av to nøstede løkker, akkurat som der.
- kap. 1.1 — hva $O$ betyr, og forskjellen på beste og
verste tilfelle.

Har du aldri sett en sorteringsalgoritme kjøre, er disse et mykere første møte:

- Sortering: boblesortering, .sort() og gitt sort_list
— boblesortering konkret, med kode som faktisk kjører.
- Lister — array- og listetenkning, som er den eneste
datastrukturen dette kapitlet trenger.
- Induksjonsbevis — valgfri fordypning, hvis du vil se hvorfor et
invariant-argument holder helt ut.

Notasjons- og pseudokodeliste

Løkke 1 — å sortere ved å sammenligne (ca. 10 min)

Tenk på en hånd med spillkort du skal få i rekkefølge. Du kan ikke lese av
«plassen» et kort skal ha; du kan bare holde to kort opp mot hverandre og se
hvilket som er lavest. Alt du får vite om verden, kommer fra slike
sammenligninger — og hvert svar er ett bit informasjon: enten er dette lavere
enn det, eller så er det ikke.

Det er nøyaktig arbeidsbetingelsen til en sammenligningsbasert sortering, og
den er verdt å ta på alvor, for den er grunnen til at det finnes en grense for
hvor rask sortering kan bli. Vi kommer tilbake til grensen i løkke 4.

De tre algoritmene i dette kapitlet — boblesortering, utvalgssortering og
innsettingssortering — er alle sammenligningsbaserte, alle kvadratiske i verste
tilfelle, og alle enkle nok til at du kan skrive dem ned uten hjelpemidler. Det
er den siste egenskapen UiO utnytter: de spør ikke om du kan implementere dem,
men om du vet nøyaktig hva de har utrettet halvveis.

Sammenligningsbasert sortering

x

Boblesortering

O(n^2)

📜Pseudokode-kontrakt: `BubbleSort`

Antagelser om representasjon. A er et array med

n

elementer indeksert
fra 0. Elementene kan sammenlignes med < og >. Sorteringen skjer i selve
arrayet, uten et nytt array ved siden av.

Prebetingelse: A inneholder $n$ sammenlignbare elementer i vilkårlig
rekkefølge. Postbetingelse: A er sortert stigende og inneholder nøyaktig
de samme elementene som før.

Procedure BubbleSort(A)
  Input:  array A med n sammenlignbare elementer, indeksert fra 0
  Output: A sortert stigende, sortert på stedet
  n = A.length
  for i = 1 to n-1:
      byttet = usant
      for j = 0 to n-i-1:
          if A[j] > A[j+1]:
              bytt A[j] og A[j+1]
              byttet = sant
      if byttet er usant:
          return

Grunnideen i én setning: hvert nabobytte flytter et større element ett hakk
til høyre, så etter runde $i$ har de $i$ største elementene funnet sin endelige
plass bakerst og trenger aldri røres igjen.

Kjøretid: den ytre løkka går $n-1$ runder, den indre går $n-i-1$ runder, og
summen er trekantsummen $\displaystyle \frac{n(n-1)}{2}$ , altså $O(n^2)$ . Linja
if byttet er usant gjør at et ferdigsortert array oppdages etter én runde: da
er kjøretiden $O(n)$ i beste tilfelle.

✏️Eksempel 1: Boblesortering runde for runde

Håndkjør BubbleSort på A = [8, 3, 5, 1, 9, 2]. Skriv opp tilstanden etter
hver runde av den ytre løkka, og si hvilke elementer som er garantert på endelig
plass etter hver runde.

Én runde av den ytre løkka er én gjennomgang av alle naboparene som fortsatt er
i spill.

Etter iterasjon $i$	Tilstand	Garantert på endelig plass	Bytter i runden
1	`[3, 5, 1, 8, 2, 9]`	de 1 største, helt til høyre: `[9]`	4
2	`[3, 1, 5, 2, 8, 9]`	de 2 største, helt til høyre: `[8, 9]`	2
3	`[1, 3, 2, 5, 8, 9]`	de 3 største, helt til høyre: `[5, 8, 9]`	2
4	`[1, 2, 3, 5, 8, 9]`	de 4 største, helt til høyre: `[3, 5, 8, 9]`	1
5	`[1, 2, 3, 5, 8, 9]`	de 5 største, helt til høyre: `[2, 3, 5, 8, 9]`	0

Sluttilstand: [1, 2, 3, 5, 8, 9]. I alt 15 sammenligninger og 9 bytter.
Les tabellen én gang til, for dette er selve eksamensspørsmålet. Etter runde
2 er [8, 9] ferdig — ikke fordi arrayet ser sortert ut der, men fordi
algoritmen garanterer det. Elementene til venstre kan fortsatt flytte seg mye:
[3, 1, 5, 2] blir til slutt [1, 2, 3, 5].
Merk også runde 5. Den gjorde null bytter, og med tidlig stopp ville

algoritmen returnert etter runde 4. Det er den lille detaljen som gir

boblesortering $O(n)$ i beste tilfelle.

📝Oppgave 1

(Innstegsoppgave, sjanger D — sorteringsegenskaper, altså at du oppgir hva en
sorteringsalgoritme garanterer.) Boblesortering kjøres på [6, 2, 7, 4].

a) Hvor mange runder gjør den ytre løkka totalt?
b) Hvilket element står garantert på endelig plass etter én runde?
c) Er boblesortering stabil, når den kun bytter naboer som står i feil
rekkefølge?

📜Invarianten for boblesortering etter

i

iterasjoner

Etter $i$ fullførte runder av den ytre løkka i BubbleSort gjelder:

De $i$ største elementene ligger på sine endelige plasser, helt til høyre i
arrayet, i riktig innbyrdes rekkefølge.

Om resten sier invarianten ingenting. De $n - i$ første elementene kan stå i
en hvilken som helst rekkefølge.

Hvorfor holder det? I runde 1 sammenlignes hvert nabopar fra venstre mot høyre.
Det største elementet vil, så snart gjennomgangen når det, vinne hver eneste
sammenligning videre og skyves helt til enden. Samme argument gjelder det nest
største i runde 2, og så videre.

En invariant er en påstand som er sann hver gang løkka har fullført en runde
— uansett hvilke tall som lå i arrayet i utgangspunktet. Det er derfor du kan
svare på spørsmålet uten å se arrayet.

📝Oppgave 2

Sjanger D

Et array med 12 elementer sorteres med boblesortering. Etter 4
fullførte runder av den ytre løkka:

a) Hvor mange elementer står garantert på endelig plass, og hvor i arrayet
ligger de?
b) Kan du si noe om elementet på indeks 0?
c) Hvor mange sammenligninger gjør den indre løkka i runde 5?

Løkke 2 — utvalgssortering og de billige byttene (ca. 12 min)

— naturlig pausepunkt —

Boblesortering flytter elementer i mange små steg. Utvalgssortering (selection
sort) gjør det motsatte: den leter først og flytter så én gang.

Framgangsmåten er den du ville brukt hvis flyttingen var dyr — for eksempel hvis
hvert «element» var en tung eske i et lager. Finn den letteste esken i hele
lageret og sett den helt til venstre. Finn den letteste av dem som er igjen, og
sett den ved siden av. Og så videre.

Poenget er at du bare gjør ett bytte per runde, uansett hvor rotete arrayet
er. Det er utvalgssorteringens ene virkelige fortrinn, og det er et fast
sant/usant-punkt.

Utvalgssortering

n-1

📜Pseudokode-kontrakt: `SelectionSort`

Antagelser om representasjon. A er et array med

n

sammenlignbare
elementer indeksert fra 0. Sorteringen skjer på stedet.

Prebetingelse: A inneholder $n$ elementer i vilkårlig rekkefølge.
Postbetingelse: A er sortert stigende.

Procedure SelectionSort(A)
  Input:  array A med n sammenlignbare elementer, indeksert fra 0
  Output: A sortert stigende, sortert på stedet
  n = A.length
  for i = 0 to n-2:
      minst = i
      for j = i+1 to n-1:
          if A[j] < A[minst]:
              minst = j
      if minst er ulik i:
          bytt A[i] og A[minst]

Grunnideen i én setning: når du har funnet det minste av de gjenværende
elementene, kan det ikke tilhøre noen senere plass, så det kan settes endelig.

Kjøretid: den indre løkka gjør $n-1$ , så $n-2$ , så $n-3$ sammenligninger og
så videre, altså $\displaystyle \frac{n(n-1)}{2}$ i alt — $O(n^2)$ . Antall bytter er
derimot høyst $n-1$ , uansett input.

✏️Eksempel 2: Utvalgssortering runde for runde

Håndkjør SelectionSort på det samme arrayet som i eksempel 1,
A = [8, 3, 5, 1, 9, 2]. Skriv opp tilstanden etter hver runde, hvilke
elementer som er endelig plassert, og hvilket bytte som ble gjort.

Etter iterasjon $i$	Tilstand	Garantert på endelig plass	Bytte i runden
1	`[1, 3, 5, 8, 9, 2]`	de 1 minste, helt til venstre: `[1]`	ja: plass 0 og 3
2	`[1, 2, 5, 8, 9, 3]`	de 2 minste, helt til venstre: `[1, 2]`	ja: plass 1 og 5
3	`[1, 2, 3, 8, 9, 5]`	de 3 minste, helt til venstre: `[1, 2, 3]`	ja: plass 2 og 5
4	`[1, 2, 3, 5, 9, 8]`	de 4 minste, helt til venstre: `[1, 2, 3, 5]`	ja: plass 3 og 5
5	`[1, 2, 3, 5, 8, 9]`	de 5 minste, helt til venstre: `[1, 2, 3, 5, 8]`	ja: plass 4 og 5

Sluttilstand: [1, 2, 3, 5, 8, 9]. I alt 15 sammenligninger og 5 bytter.
Sammenlign med eksempel 1. Nøyaktig samme array, nøyaktig samme antall
sammenligninger (15), men 5 bytter mot boblesorteringens 9. Og den ferdige delen
vokser fra motsatt ende: utvalgssortering låser de minste til venstre, mens
boblesortering låser de største til høyre.
Se på runde 2 og legg merke til hvor langt 2-tallet flyttet: fra indeks 5 til

indeks 1, i ett hopp, forbi 5, 8 og 9. Det er dette hoppet som gjør

utvalgssortering ustabil — vi kommer tilbake til det i løkke 4.

📜Invarianten for utvalgssortering etter

i

iterasjoner

Etter $i$ fullførte runder av den ytre løkka i SelectionSort gjelder:

De $i$ minste elementene ligger på sine endelige plasser, helt til venstre i
arrayet, i riktig innbyrdes rekkefølge.

Om resten sier invarianten ingenting.

Legg merke til hvor lik og likevel hvor motsatt den er bobleinvarianten. Begge
låser $i$ elementer etter $i$ runder — men boblesortering låser de største til
høyre, utvalgssortering de minste til venstre. Å blande disse to er den
enkeltfeilen som koster flest poeng på sjanger D.

Et ekstra faktum som spørres om direkte: utvalgssortering gjør minimalt antall
bytter av alle de tre, høyst $n-1$ . Den gjør derimot alltid
$\displaystyle \frac{n(n-1)}{2}$ sammenligninger, også på et ferdigsortert array.

📝Oppgave 3

Sjanger D

Et lager har 20 pakker som skal sorteres etter vekt.

a) Etter 6 runder med utvalgssortering — hvilke pakker står garantert
endelig, og på hvilke indekser?
b) Etter 6 runder med boblesortering — hvilke pakker står garantert endelig,
og på hvilke indekser?
c) Hvis hver flytting av en pakke er fysisk tung, men hver sammenligning er
gratis — hvilken av de to velger du, og hvorfor?

Løkke 3 — innsettingssortering og prefikset som ikke er endelig (ca. 13 min)

Innsettingssortering (insertion sort) er den du faktisk bruker på en hånd med
kort. Du holder en sortert vifte i venstre hånd, tar opp ett nytt kort og skyver
det inn på rett plass i vifta.

Den viktige detaljen — og den UiO spør om oftere enn noe annet i dette kapitlet —
er hva «rett plass i vifta» betyr. Det betyr rett plass blant kortene du har
sett så langt. Neste kort du trekker, kan godt være lavere enn alle sammen, og
da må hele vifta forskyves. Innsettingssortering plasserer altså ingenting
endelig før den er helt ferdig.

Innsettingssortering

i

📜Pseudokode-kontrakt: `InsertionSort`

Antagelser om representasjon. A er et array med

n

sammenlignbare
elementer indeksert fra 0. Sorteringen skjer på stedet, med én hjelpevariabel.

Prebetingelse: A inneholder $n$ elementer i vilkårlig rekkefølge.
Postbetingelse: A er sortert stigende.

Procedure InsertionSort(A)
  Input:  array A med n sammenlignbare elementer, indeksert fra 0
  Output: A sortert stigende, sortert på stedet
  n = A.length
  for i = 1 to n-1:
      x = A[i]
      j = i - 1
      while j >= 0 and A[j] > x:
          A[j+1] = A[j]
          j = j - 1
      A[j+1] = x

Invarianten i én setning: rett før runde $i$ er A[0..i-1] sortert
innbyrdes, og runden utvider det sorterte prefikset med ett element.

Kjøretid: den ytre løkka går $n-1$ runder. Den indre while-løkka gjør i
verste tilfelle $i$ forskyvninger — det skjer når arrayet er omvendt sortert —
og summen blir $\displaystyle \frac{n(n-1)}{2}$ , altså $O(n^2)$ . Er arrayet allerede sortert,
stopper while-løkka med én gang hver runde, og totalen blir $O(n)$ .

Merk at A[j] > x er strengt større: elementet skyves aldri forbi et likt
element. Det er derfor innsettingssortering er stabil.

✏️Eksempel 3: Innsettingssortering — prefikset som lyver

Håndkjør InsertionSort på A = [8, 3, 5, 1, 9, 2]. Skriv opp tilstanden etter
hver runde, og avgjør for hver runde om det sorterte prefikset også er
endelig plassert.

Fasit for hele sorteringen er [1, 2, 3, 5, 8, 9] — den trenger vi for å kunne
avgjøre siste kolonne.

Etter iterasjon $i$	Tilstand	Sortert prefiks	Endelig plassert?	Forskyvninger
1	`[3, 8, 5, 1, 9, 2]`	`[3, 8]`	nei	1
2	`[3, 5, 8, 1, 9, 2]`	`[3, 5, 8]`	nei	1
3	`[1, 3, 5, 8, 9, 2]`	`[1, 3, 5, 8]`	nei	3
4	`[1, 3, 5, 8, 9, 2]`	`[1, 3, 5, 8, 9]`	nei	0
5	`[1, 2, 3, 5, 8, 9]`	`[1, 2, 3, 5, 8, 9]`	ja — men først nå, fordi den er ferdig	4

Sluttilstand: [1, 2, 3, 5, 8, 9]. I alt 12 sammenligninger og 9
forskyvninger.
Se på runde 4. Prefikset er [1, 3, 5, 8, 9] — fem elementer, pent sortert.
Fasiten begynner med [1, 2, 3, 5, 8]. Fire av de fem står altså på feil indeks,
og det eneste som skal til for å velte dem, er 2-tallet som ligger igjen til
slutt. Da forskyves fire elementer på én gang.

Dette er kapitlets skarpeste sant/usant-punkt. «Etter $i$ iterasjoner av
innsettingssortering står de $i$ første elementene på endelig plass» er

usant. Riktig formulering er: de $i+1$ første elementene er sortert
innbyrdes.
Kontrollregning. Antall forskyvninger, 9, er det samme som antall bytter
boblesortering brukte på det samme arrayet i eksempel 1. Det er ingen

tilfeldighet: begge algoritmene fjerner nøyaktig ett feilstilt par per
elementflytting, og arrayet har 9 slike par.

📜Invarianten for innsettingssortering etter

i

iterasjoner

Etter $i$ fullførte runder av den ytre løkka i InsertionSort gjelder:

De $i+1$ første elementene er sortert innbyrdes — men ikke nødvendigvis på
sine endelige plasser.

Sammenlign de tre invariantene, som ett samlet puggekort:

Algoritme	Etter $i$ iterasjoner	Endelig plassert?
Boblesortering	de $i$ største ligger helt til høyre	ja
Utvalgssortering	de $i$ minste ligger helt til venstre	ja
Innsettingssortering	de $i+1$ første er sortert innbyrdes	nei

To av tre garanterer endelig plassering; den tredje gjør det ikke. Å vite hvilken
som er hvilken, er verdt et helt poeng på hvert eneste sett.

Typiske feil

Alle fire er dokumenterte poengtap på sjanger D.

- Å bytte om på hvilken ende som blir ferdig. Boblesortering låser de
største til høyre; utvalgssortering låser de minste til venstre. Et
minnetriks: bobler stiger til overflaten, altså til enden av arrayet.
- Å tro at innsettingssortering plasserer endelig. Den sorterer prefikset
innbyrdes. Et element som kommer senere, kan velte hele prefikset ett hakk. Se
eksempel 3, runde 4.
- Å påstå at utvalgssortering er stabil. Byttet flytter et element over lang
avstand og kan hoppe forbi et likt element. Boblesortering og
innsettingssortering flytter derimot bare forbi strengt større elementer,
og er stabile.
- Å blande antall bytter med antall sammenligninger. Utvalgssortering har
færrest bytter (høyst $n-1$ ), men like mange sammenligninger som
boblesortering ( $\displaystyle \frac{n(n-1)}{2}$ ). Spørsmålet på eksamen sier alltid hvilken
av de to det gjelder — les det ordet.

Én til, som gjelder hele faget: å bruke $n$ uten å si hva det er. Dette er
felle #10 i bokas feilregister — å oppgi kjøretid eller drøfte uten å
definere problemstørrelsen — og den gir eksplisitt trekk. Skriv « $n$ er antall
elementer som skal sorteres» én gang, og du er ferdig med den.

📝Oppgave 4

Sjanger D

Arrayet [4, 9, 2, 7, 3, 8] sorteres med innsettingssortering.

a) Hva er tilstanden etter 3 fullførte runder av den ytre løkka?
b) Står noen av elementene i det sorterte prefikset garantert på sin endelige
plass?
c) Hvor mange forskyvninger gjorde runde 4?

Løkke 4 — stabilitet, in-place og grensen på $n \log n$ (ca. 15 min)

— naturlig pausepunkt —

Nå kommer de to egenskapene som avgjør flest sant/usant-punkter, og de er begge
lettere enn de høres ut.

Tenk deg en deltakerliste fra et løp, allerede sortert alfabetisk på etternavn.
Nå vil du sortere den på klubb. To løpere fra samme klubb — hva skjer med den
alfabetiske rekkefølgen mellom dem?

Svarer algoritmen «den beholdes», er den stabil. Svarer den «det kommer an
på», er den ustabil. Det er hele begrepet.

Stabil sortering

En sortering er stabil hvis elementer med lik nøkkel beholder sin innbyrdes rekkefølge fra input til output. Boblesortering, innsettingssortering, flettesortering, counting sort og radix sort er stabile. Utvalgssortering, heapsort og kvikksortering er det ikke . Hvorfor det betyr noe: stabilitet lar deg sortere på flere nøkler etter hverandre. Sorterer du først på etternavn og deretter stabilt på klubb, er resultatet sortert på klubb med etternavn som andrenøkkel — gratis.

In-place — sortering på stedet

O(1)

✏️Eksempel 4: Stabilitet demonstrert på samme data

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

Hansen(3), Berg(1), Dahl(3), Ali(2)

Lista skal sorteres på startgruppe. Kjør både innsettingssortering og
utvalgssortering, og sammenlign resultatene.

Innsettingssortering (stabil):

Berg(1), Ali(2), Hansen(3), Dahl(3)

Utvalgssortering (ustabil):

Berg(1), Ali(2), Dahl(3), Hansen(3)

Begge er korrekt sortert på startgruppe: 1, 2, 3, 3. Forskjellen er
rekkefølgen mellom Hansen og Dahl, som begge har gruppe 3.

Hvorfor skjer det? Innsettingssortering skyver Dahl bakover kun så lenge
elementet foran er strengt større. Når den møter Hansen(3), stopper den —
og Dahl blir liggende etter Hansen, slik den lå i input.

Utvalgssortering, derimot, leter opp minste gjenværende og bytter det inn på
plassen. I runden som skal fylle indeks 2, finner den Dahl(3) som minste blant
de gjenværende, og bytter Hansen ut til den plassen Dahl sto på. Ett langt
hopp — og den innbyrdes rekkefølgen er borte.

Regelen du kan lene deg på: en sortering som bare flytter elementer forbi
strengt større naboer er stabil. En sortering som bytter over lang avstand,
er det ikke.

Merk at «ustabil» ikke betyr «feil». Utvalgssorteringens resultat er en
fullgod sortering på startgruppe. Ustabiliteten betyr bare at du ikke kan stole
på informasjonen som lå i den opprinnelige rekkefølgen.

📝Oppgave 5

Sjanger D, eksamensnivå

En liste over 500 bøker er allerede sortert
alfabetisk på tittel. Du vil nå ha den sortert på utgivelsesår, og innenfor hvert
år skal titlene fortsatt stå alfabetisk.

a) Hvilken egenskap må sorteringsalgoritmen ha?
b) Hvilke av de tre algoritmene i dette kapitlet kan du bruke?
c) En kollega foreslår å sortere på år og deretter sortere alfabetisk på
tittel. Hva blir resultatet?

Kjøretidstabellen — puggeflaten

Dette er tabellen sant/usant-punktene hentes fra. Lær den som et bilde.

Algoritme	Beste	Verste	Forventet	Stabil?	In-place?	Særtrekk
Boblesortering	$O(n)$ med tidlig stopp	$O(n^2)$	$O(n^2)$	ja	ja	bytter kun naboer
Utvalgssortering	$O(n^2)$	$O(n^2)$	$O(n^2)$	nei	ja	minimalt antall bytter, høyst $n-1$
Innsettingssortering	$O(n)$	$O(n^2)$	$O(n^2)$	ja	ja	best på nesten sorterte data

Tre ting å legge merke til, fordi de alle har vært sant/usant-punkter:
1. Utvalgssortering har ingen god dag. Den er

O(n^2)

selv på et
ferdigsortert array, fordi den uansett må lete gjennom resten for å bevise at
den har funnet minsteverdien.

2. Boblesorteringens $O(n)$ krever tidlig stopp. Uten byttet-flagget i

pseudokoden er også beste tilfelle $O(n^2)$ . Sier oppgaven bare
«boblesortering», er det trygt å nevne begge deler.
3. Alle tre er in-place, bare to er stabile. Utvalgssortering er unntaket.

📜Nedre grensen for sammenligningsbasert sortering

Ingen sammenligningsbasert sortering kan garantere å sortere

n

elementer med
færre enn omtrent

n \log_2 n

sammenligninger. Vi skriver det

$\Omega(n \log n),$

der $\Omega$ er nedre grense — motstykket til $O$ fra
kap. 1.1.

Intuisjonen, i tre setninger. Hver sammenligning gir ett ja/nei-svar, altså
ett bit informasjon. Med $n$ elementer finnes det $n!$ mulige rekkefølger, og
algoritmen må kunne skille alle fra hverandre. Skal $k$ ja/nei-svar skille mellom
$n!$ muligheter, må $2^k \ge n!$ , og det gir $k \ge \log_2(n!)$ , som vokser som
$n \log n$ .

Konsekvensen er verdt å merke seg: flettesortering og heapsort med sine
$O(n \log n)$ er ikke bare «bra» — de er så gode som det i det hele tatt går an å
bli, så lenge algoritmen bare sammenligner. Vil du under, må du slutte å
sammenligne og begynne å utnytte hva verdiene faktisk er. Det er nøyaktig det
counting sort og radix sort gjør i kap. 2.3.

Beviset skisseres nærmere i kap. 2.2, der beslutningstreet
tegnes ut.

✏️Eksempel 5: Eksamensnivå — fire påstander

(Sjanger D, sant/usant med begrunnelse.) Avgjør sant eller usant, og begrunn hver
med én setning.

a) Etter 3 iterasjoner av utvalgssortering står de 3 minste elementene på
endelig plass.
b) Etter 3 iterasjoner av innsettingssortering står de 3 første elementene på
endelig plass.
c) Boblesortering gjør færre bytter enn utvalgssortering på et vilkårlig
array.
d) En sammenligningsbasert sortering kan i beste tilfelle bruke $O(n)$
sammenligninger.

a) Sant. Det er nøyaktig utvalgssorteringens invariant: etter

i

runder er
de

i

minste endelig plassert, helt til venstre.

b) Usant. Innsettingssortering sorterer de $i+1$ første innbyrdes, men et
element som kommer senere kan forskyve hele prefikset. Ingenting er endelig før
algoritmen er ferdig.

c) Usant. Det er motsatt: utvalgssortering gjør høyst $n-1$ bytter,
boblesortering kan gjøre opp til $\displaystyle \frac{n(n-1)}{2}$ . Merk fella i formuleringen —
«færre bytter», ikke «færre sammenligninger». På sammenligninger er de like.

d) Sant. Nedre grensen $\Omega(n \log n)$ gjelder verste tilfelle. I
beste tilfelle klarer innsettingssortering seg med $n-1$ sammenligninger på et
ferdigsortert array, altså $O(n)$ .

Om antigjettingen. Fire påstander der to er sanne og to usanne — det er
typisk. Gjetter du på alle fire, får du i snitt to riktige, og etter skaleringen
er to riktige av fire verdt null. Sikkerheten er hele poenget, og den kommer fra
tabellen og de tre invariantene, ikke fra magefølelse.

Om formen. Sensor ber om «én setning». En setning som navngir invarianten
eller egenskapen holder; en setning som bare gjentar påstanden med motsatt
fortegn, gjør det ikke.

📝Oppgave 6

Sjanger D, eksamensnivå

For hver av situasjonene under: hvilken av de tre
algoritmene i dette kapitlet passer best, og hva er kjøretiden?

a) Et array på 10 000 elementer som allerede er nesten sortert — bare noen få
elementer står feil.
b) En liste med tunge objekter der en flytting koster mye, men en
sammenligning er billig.
c) En liste sortert på fornavn som nå skal sorteres på fødselsår, med fornavn
beholdt som andrenøkkel.

📝Oppgave 7

Sjanger D, krevende

Påstanden under er hentet fra en tenkt besvarelse. Finn
alle feilene, og skriv en korrekt versjon.

«Utvalgssortering er den beste av de tre fordi den er stabil og har $O(n)$ i
beste tilfelle. Innsettingssortering plasserer de $i$ første elementene endelig
etter $i$ runder, og boblesortering plasserer de $i$ minste helt til venstre.
Alle tre trenger et hjelpearray på $n$ plasser.»

📝Oppgave 8

Sjanger D, krevende

Et array A har $n$ elementer, og du får vite at nøyaktig
ett element står på feil plass: det ligger helt til venstre, men skulle ligget
helt til høyre. Resten er sortert.

a) Hvor mange runder må boblesortering med tidlig stopp gjøre før den
returnerer, og hva blir kjøretiden?
b) Hvor mange forskyvninger gjør innsettingssortering totalt, og hva blir
kjøretiden?
c) Hva blir utvalgssorteringens kjøretid?

Begrepsbank

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

Invariant

i

Bobleinvarianten

i

Utvalgsinvarianten

i

Innsettingsinvarianten

i

Antall bytter i utvalgssortering

n-1

Antall sammenligninger i utvalgssortering

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

Innsettingssortering på nesten sorterte data

O(n)

Boblesortering med tidlig stopp

O(n)

Nabobytte og stabilitet

Regelen bak alle stabilitetssvar: en sortering som bare flytter elementer forbi strengt større naboer, kan ikke bytte om på to like nøkler, og er derfor stabil. Boblesortering (A[j] > A[j+1]) og innsettingssortering (A[j] > x) oppfyller den. Utvalgssortering gjør det ikke, fordi den bytter over lang avstand.

Nøkkel og satellittdata

Nøkkelen er verdien det sorteres på; satellittdataene er alt annet elementet bærer med seg. En bok sortert på utgivelsesår har året som nøkkel og tittelen som satellittdata. Stabilitet handler utelukkende om elementer med lik nøkkel og ulike satellittdata. Uten satellittdata er stabilitet et tomt begrep — to like tall kan ikke skilles.

Sortering på flere nøkler

Sorterer du gjentatte ganger med en stabil algoritme, og tar den minst viktige nøkkelen først, ender du med et resultat sortert på hovednøkkelen med de andre som andrenøkler. Rekkefølgen er ikke intuitiv: den siste sorteringen styrer hovedrekkefølgen. Dette prinsippet er også hele maskineriet i radix sort, kap. 2.3 .

Nedre grense for sammenligningsbasert sortering

\Omega(n \log n)

Beslutningstre

n!

Verste tilfelle for de tre kvadratiske

O(n^2)

Beste tilfelle for de tre kvadratiske

O(n)

Sortert prefiks kontra endelig plassering

To ulike garantier, som sjanger D spiller på hele tiden. Sortert innbyrdes betyr at elementene står i riktig rekkefølge seg imellom. Endelig plassert betyr at ingen senere operasjon vil flytte dem. Innsettingssortering gir det første, ikke det andre. Boblesortering og utvalgssortering gir begge deler, men bare for sin halvdel av arrayet.

Å telle iterasjoner

i

Sjanger D — sorteringsegenskaper og valg

Del 1-sjangeren dette kapitlet trener: 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 %). Fordi den ligger i den auto-rettede delen med antigjettings-skalering, gir usikre svar null. Kjøretidstabellen og de tre invariantene er det du skal kunne hjelpemiddelfritt.

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.

2.1 Sammenligningsbaserte sorteringer og invarianter

Forkunnskaper

Løkke 1 — å sortere ved å sammenligne (ca. 10 min)

Løkke 2 — utvalgssortering og de billige byttene (ca. 12 min)

Løkke 3 — innsettingssortering og prefikset som ikke er endelig (ca. 13 min)

Løkke 4 — stabilitet, in-place og grensen på nlog⁡nn \log nnlogn (ca. 15 min)

Kjøretidstabellen — puggeflaten

Begrepsbank

Løkke 4 — stabilitet, in-place og grensen på $n \log n$ (ca. 15 min)