2.3 Utvelgelse — Partition, Randomized-Select og Select

Finne det `i`-te minste elementet uten å sortere: `Partition`, `Randomized-Select` og `Select` (median av medianer) med kjøretider.

45 min

5 oppgaver

UtvelgelsePartitionRandomized-SelectSelect

Din fremgang i kapitlet

0 / 5 oppgaver

Kapitlets plass i kurset

Bygger på

2.1Sammenligningsbaserte sorteringer

Brukes videre i

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

Utvelgelse er registrert i 8 av de 17 settene i grunnlaget (47 %).
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.

Temaet er delt i to når det gjelder prioritet:

- Partition må sitte. Den er motoren i Quicksort, den er en fast
håndkjøringsoppgave, og den dukker opp som «fyll inn den manglende linjen».
Prioritet: bør sitte.
- Select — median av medianer — er noe du skal kjenne til. Du skal kunne
si at den garanterer $\Theta(n)$ i verste tilfelle, og hvorfor
Randomized-Select ikke gjør det. Selve analysen er ikke pensum å utlede.
Prioritet: kjenne til.

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

- Sjanger C — håndkjøring, altså at du utfører algoritmen steg for steg på
papir og oppgir bare sluttilstanden. For Partition er svarformen arrayet
etterpå og pivotens sluttindeks q.
- Sjanger E — kjøretidskunnskap, altså at du oppgir kjøretiden i det
strammeste uttrykket som er riktig. Her ligger kapitlets faste felle: å
oppgi Randomized-Select sitt verste tilfelle som $\Theta(n)$ . Det er
forventet kjøretid; verste tilfelle er $\Theta(n^2)$ .

Slik er kapitlet lagt opp (45 min):

Innhold	Tid
Utvelgelsesproblemet	ca. 6 min
`Partition`, linje for linje	ca. 14 min
`Randomized-Select`	ca. 15 min
`Select` og den garanterte lineære tiden	ca. 10 min

Forkunnskaper

- kap. 2.1 — sammenligningsbaserte sorteringer. Fra det
kapitlet: Quicksort partisjonerer om et pivot og sorterer de to sidene
rekursivt, og den er $\Theta(n\lg n)$ forventet og $\Theta(n^2)$ i verste
tilfelle. Vi bruker den samme Partition her, men denne gangen bare på
den ene siden.
- kap. 1.1 — de asymptotiske symbolene. Skillet mellom
«forventet» og «verste tilfelle» er selve poenget i dette kapitlet.
- kap. 1.5 — iterasjonsmetoden. Rekurrensen
$T(n) = T(n/2) + \Theta(n)$ løses lettest ved å summere en geometrisk rekke.

Notasjons- og pseudokodeliste

Utvelgelsesproblemet (~6 min)

En kommune har 240 000 innbyggere og vil vite medianinntekten — beløpet der
halvparten tjener mindre og halvparten mer. Den enkleste framgangsmåten er å
sortere alle inntektene og lese av det midterste tallet. Det koster
$\Theta(n\lg n)$ .

Men spørsmålet er mye smalere enn en sortering. Vi vil ha ett tall, ikke
hele rekkefølgen. Og det viser seg at det ene tallet kan hentes ut i lineær
tid.

Utvelgelsesproblemet

n

Ordensstatistikk og median

i

📝Oppgave 1

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

Forklar hva utvelgelsesproblemet er, og hvorfor en sortering er en
«overdimensjonert» løsning på det.

`Partition`, linje for linje (~14 min)

Både utvelgelsesalgoritmene og Quicksort hviler på den samme rutinen. Den er
verdt å kunne utenat, fordi den er en fast håndkjøringsoppgave og fordi den
dukker opp i «hvilken linje mangler?»-varianten.

Partition velger siste element i delen som pivot og går gjennom delen én gang
fra venstre. Underveis holder den et skille: alt til venstre for skillet er
mindre enn eller lik pivoten. Til slutt settes pivoten inn på skilleplassen.

📜Pseudokode-kontrakt: `Partition`

Antagelser om representasjon. Arrayet er A[1..n], indeks fra 1. Kallet
arbeider på delen A[p..r] med p <= r. Pivoten er siste element, A[r].
Rutinen går på stedet.

Prebetingelse: p <= r.
Postbetingelse: rutinen returnerer en indeks q med p <= q <= r, slik at
A[p..q-1] alle er $\le$ A[q] og A[q+1..r] alle er $>$ A[q]. Elementet
på plass q er pivoten, og det står på den plassen det ville hatt i et ferdig
sortert array.

Partition(A, p, r)
  Input:  array A[p..r]
  Output: pivotens sluttindeks q
  x = A[r]
  i = p - 1
  for j = p to r - 1
      if A[j] <= x
          i = i + 1
          bytt A[i] og A[j]
  bytt A[i+1] og A[r]
  return i + 1
  Kjoeretid: Theta(r - p + 1)

Invarianten i én setning: rett før hver runde med indeks j er alt i
A[p..i] mindre enn eller lik pivoten, alt i A[i+1..j-1] er større enn
pivoten, og A[r] er pivoten selv.

Legg merke til at i starter på p - 1. Den venstre regionen er tom til
å begynne med, og i peker alltid på det siste elementet i den. Er alle
elementene større enn pivoten, blir i liggende på p - 1, og pivoten havner
på plass p.

Kjøretid: for-løkka gjør r - p runder med konstant arbeid, pluss ett
bytte til slutt — altså $\Theta(r-p+1)$ , lineært i lengden på delen.

✏️Eksempel 1: `Partition` med siste element som pivot

Sju måleverdier ligger slik: A = 53, 18, 67, 24, 71, 39, 45 (indeks fra 1).

Kjør Partition(A, 1, 7). Oppgi arrayet etter partisjoneringen og pivotens
sluttindeks q.

Pivoten er A[7] = 45, og i starter på 0.

`j`	Test	`i` etterpå	Array etter runden
1	`A[1]=53` $>$ 45	—	`53, 18, 67, 24, 71, 39, 45`
2	`A[2]=18` $\le$ 45	1	`18, 53, 67, 24, 71, 39, 45`
3	`A[3]=67` $>$ 45	—	`18, 53, 67, 24, 71, 39, 45`
4	`A[4]=24` $\le$ 45	2	`18, 24, 67, 53, 71, 39, 45`
5	`A[5]=71` $>$ 45	—	`18, 24, 67, 53, 71, 39, 45`
6	`A[6]=39` $\le$ 45	3	`18, 24, 39, 53, 71, 67, 45`

Etter løkka står i på 3. Det siste steget bytter A[i+1] og A[r], altså
A[4] og A[7].
Sluttilstanden — det du ville levert på eksamen:
Array: 18, 24, 39, 45, 71, 67, 53, og q = 4.
Kontrollen er enkel: alt til venstre for plass 4 er

\le

45, og alt til høyre er

>

45. Legg merke
til at høyresiden ikke er sortert — Partition lover ingenting om

rekkefølgen innenfor hver side.
Oppgaven ba om arrayet og q. Ba den bare om q, er det ene tallet hele

svaret.

📝Oppgave 2

Eksamensnivå, sjanger C

Kjør Partition(A, 1, 6) på A = 12, 45, 7, 33, 21, 19 med siste element som
pivot.

a) Oppgi arrayet etter partisjoneringen.
b) Oppgi pivotens sluttindeks q.

📝Oppgave 3

Eksamensnivå, sjanger F

En kandidat skriver: «Etter Partition er venstresiden sortert stigende og
høyresiden sortert stigende.»

Stemmer det? Svar ja eller nei, og begrunn.

`Randomized-Select` (~15 min)

Nå kommer ideen som gjør utvelgelse lineær. Quicksort partisjonerer og går
rekursivt inn i begge sidene. Men leter du etter det $i$ -te minste
elementet, vet du etter partisjoneringen nøyaktig hvilken side svaret ligger
på — og den andre siden kan kastes.

Etter Partition(A, p, r) som returnerer q, står pivoten som nummer
k = q - p + 1 innenfor delen. Er i = k, er pivoten svaret. Er i < k,
ligger svaret til venstre. Er i > k, ligger det til høyre, og du leter der
etter det (i - k)-te minste — fordi k elementer nå er strøket bort under
det du leter etter.

📜Pseudokode-kontrakt: `Randomized-Select`

Antagelser om representasjon. Arrayet er A[1..n], indeks fra 1. Kallet
utenfra er Randomized-Select(A, 1, A.length, i) med
1 <= i <= A.length. Elementene antas forskjellige.
Randomized-Partition bytter et tilfeldig element i delen til plass r og
kaller Partition.

Prebetingelse: 1 <= i <= r - p + 1.
Postbetingelse: rutinen returnerer det $i$ -te minste elementet i A[p..r].
Svaret er alltid riktig; det er bare kjøretiden som avhenger av de tilfeldige
trekkene.

Randomized-Select(A, p, r, i)
  Input:  array A[p..r] og et ordenstall i
  Output: det i-te minste elementet i A[p..r]
  if p == r
      return A[p]
  q = Randomized-Partition(A, p, r)
  k = q - p + 1
  if i == k
      return A[q]
  else if i < k
      return Randomized-Select(A, p, q-1, i)
  else
      return Randomized-Select(A, q+1, r, i-k)
  Kjoeretid: Theta(n) forventet, Theta(n^2) verste

Grunnideen i én setning: partisjoneringen forteller hvilken side svaret
ligger på, og den andre siden trenger aldri å ses på igjen.

Intuisjon for hvorfor det blir lineært. Antar vi at hvert kall halverer
delen, blir arbeidet $n + n/2 + n/4 + n/8 + \dots$ , og den summen er mindre
enn $2n$ uansett hvor mange ledd du tar med. Rekurrensen
$T(n) = T(n/2) + \Theta(n)$ gir altså $\Theta(n)$ — i motsetning til
Quicksorts $T(n) = 2T(n/2) + \Theta(n) = \Theta(n\lg n)$ , der begge sidene
må behandles. Det er den ene forkastede halvdelen som er hele gevinsten.

Kjøretid: $\Theta(n)$ forventet. Verste tilfelle er $\Theta(n^2)$ : gir
hvert pivotvalg en deling som skiller av bare ett element, blir rekurrensen
$T(n) = T(n-1) + \Theta(n)$ .

✏️Eksempel 2: `Randomized-Select` finner det fjerde minste

Ni sensorutslag ligger slik: A = 38, 15, 72, 9, 54, 27, 63, 41, 20
(indeks fra 1). Vi vil ha det fjerde minste, altså $i = 4$ .

Her er kjøringen med disse tilfeldige pivotvalgene: først element nummer 5,
deretter nummer 2 i den gjenværende delen, deretter nummer 3, deretter nummer
4. (På eksamen er pivotene oppgitt eller valgt av deg; her viser vi ett
konkret løp.)

Følg hvilken del som står igjen etter hvert kall.

Kall	Del	Pivot	`q`	`k`	Hva som skjer
1	`A[1..9]`	54	7	7	`i` = 4 $<$ `k` = 7: fortsett i `A[1..6]`
2	`A[1..6]`	15	2	2	`i` = 4 $>$ `k` = 2: fortsett i `A[3..6]` med `i` = 2
3	`A[3..6]`	38	5	3	`i` = 2 $<$ `k` = 3: fortsett i `A[3..4]`
4	`A[3..4]`	27	4	2	`i == k` = 2, svaret er `A[4]` = 27

Sluttilstanden — svaret: 27
Kontroll: sortert er arrayet 9, 15, 20, 27, 38, 41, 54, 63, 72, og det
fjerde minste er 27 — men vi kom fram til det uten å
sortere.
Legg merke til hvordan i endrer seg. I det andre kallet gikk vi til

høyre side og satte i = 4 - 2 = 2: to elementer (pivoten og det ene til

venstre for den) ligger nå garantert under det vi leter etter, og er strøket
fra regnskapet. Å glemme dette fratrekket er den vanligste feilen i
håndkjøring av utvelgelse.

Tell arbeidet. Delene som ble partisjonert hadde lengde 9, 6, 4 og 2 —
til sammen 21 elementgjennomganger, ikke $9 \lg 9 \approx 29$ . Forskjellen
vokser fort med $n$ .

📝Oppgave 4

Eksamensnivå, sjanger E

a) Hva er forventet kjøretid for Randomized-Select?
b) Hva er verste-tilfelle-kjøretiden, og hvordan oppstår den?
c) Hvorfor er Quicksort

\Theta(n\lg n)

forventet når
Randomized-Select er

\Theta(n)

forventet, når begge bruker samme
partisjonering?

📝Oppgave 5

Eksamensnivå, sjanger C

A = 30, 12, 47, 8, 25 (indeks fra 1), og du kjører Randomized-Select for

i = 2

. Det tilfeldige valget faller hver gang på siste element i den
gjeldende delen, altså oppfører algoritmen seg som Partition uten
omstokking.

Oppgi hvilke deler som partisjoneres, og hva svaret blir.

`Select` og den garanterte lineære tiden (~10 min)

Randomized-Select er rask nesten alltid, men gir ingen garanti. Det finnes en
variant som gjør det: Select, ofte kalt median av medianer. Den er
$\Theta(n)$ i verste tilfelle.

Dette er et tema du skal kjenne til: du skal kunne si hva den garanterer og
hvordan pivoten velges, ikke utlede analysen.

`Select` (median av medianer)

i

Typiske feil

Den første koster hele oppgaven.

- Å oppgi Randomized-Select sitt verste tilfelle som $\Theta(n)$ . Dette
er felle #9 — feil kjøretidsfakta. $\Theta(n)$ er forventet
kjøretid; verste tilfelle er $\Theta(n^2)$ . Det er Select som har
$\Theta(n)$ i verste tilfelle, og de to må ikke forveksles.
- Å glemme fratrekket i i. Fortsetter du i høyre del, leter du etter det
(i - k)-te minste, ikke det $i$ -te. De k elementene til og med pivoten er
strøket fra regnskapet.
- Å tro at Partition sorterer sidene. Den lover bare at venstresiden er
$\le$ pivoten og høyresiden $>$ pivoten. Rekkefølgen innenfor hver side er
vilkårlig.
- Å la i starte feil sted. i = p - 1, ikke i = p. Er alle elementene
større enn pivoten, skal pivoten havne helt til venstre, på plass p.
- Å oppgi mer enn det som er spurt om. Ber oppgaven om q, er tallet hele
svaret. Ber den om arrayet og q, skal begge med.

Og den gjennomgående: å skrive $\Theta$ der bare $O$ er vist. Har du bare
begrunnet en øvre grense, skriv $O$ .

Kjøretidene samlet

Dette er kapitlets puggeflate. Eksamen er hjelpemiddelfri, så tabellen må ligge
i hodet — og kolonnen «forventet mot verste» er der poengene faller.

Operasjon	Forventet	Verste	Krav / egenskap
`Partition`	$\Theta(n)$	$\Theta(n)$	ett gjennomløp, på stedet; pivoten er siste element
`Randomized-Partition`	$\Theta(n)$	$\Theta(n)$	ett tilfeldig bytte før partisjoneringen
`Randomized-Select`	$\Theta(n)$	$\Theta(n^2)$	kaster den ene siden; ingen garanti
`Select` (median av medianer)	$\Theta(n)$	$\Theta(n)$	garantert; grupper på fem; store konstanter
Minimum eller maksimum	$\Theta(n)$	$\Theta(n)$	ett gjennomløp med én sammenligning per element
Median via sortering	$\Theta(n\lg n)$	$\Theta(n\lg n)$	korrekt, men gjør mer arbeid enn nødvendig
`Quicksort`	$\Theta(n\lg n)$	$\Theta(n^2)$	går rekursivt inn i begge sidene

Én presisering som er verdt å ta med seg. Sortering kan ikke gjøres i
lineær tid med sammenligninger, men utvelgelse kan. Det er ingen motsetning:
utvelgelse er et mindre problem, og

\Omega(n\lg n)

-grensen gjelder bare
sortering.

Begrepsbank

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

`Partition`

\le

Invarianten i `Partition`

\le

`Randomized-Partition`

\Theta(r-p+1)

`Randomized-Select`

i

`Select` (median av medianer)

\Theta(n)

Ordenstallet `k` i en deling

pivotens plassering innenfor delen, regnet som k = q - p + 1 . Er i == k, er pivoten svaret. Er i < k, ligger svaret til venstre. Er i > k, ligger det til høyre, og du leter videre etter det (i - k) -te minste. Fratrekket i - k er den vanligste håndkjøringsfeilen i denne sjangeren.

Utvelgelse mot sortering

\Theta(n)

Ordensstatistikk

i

Median

n

Grupper på fem i `Select`

\lceil n/5 \rceil

Forventet mot garantert kjøretid

\Theta(n)

Rekurrensen

T(n) = T(n/2) + \Theta(n)

\Theta(n)

Sjanger C — håndkjøring

oppgavetypen der du utfører en navngitt algoritme steg for steg og oppgir sluttilstanden. For Partition er svarformen arrayet etterpå og pivotens sluttindeks q — begge deler når begge er spurt om. Ingen ekstra uttelling for å forklare algoritmen.

Sjanger E — kjøretidskunnskap

\Theta(n^2)

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.