Tilbake
6.1

6.1 Sortering: boblesortering, `.sort()` og gitt `sort_list`

Sortere for hånd med boblesortering, bruke den innebygde .sort()/sorted(), og bruke en utlevert sort_list — for å rangere rader i en tabell.

50 min
8 oppgaver
Sorteringboblesortering`.sort()`gitt `sort_list`
Din fremgang i kapitlet
0 / 8 oppgaver
Kapitlets plass i kurset
Forkunnskaper

- kap. 3.1 — lister, indeksering og de innebygde snarveiene sorted, max og min.
- kap. 3.2 — 2D-lister, altså tabeller der hver rad selv er ei liste.
- kap. 1.3 — løkker og range. Du bør ha sittende at range(start, stopp, steg) stopper FØR stopp.

Vil du se det samme stoffet i en mykere innpakning først, dekker Søke- og sorteringsalgoritmer sortering på videregående-nivå.

Har du aldri programmert, holder to ord herfra: en liste er flere verdier under ett navn, i en bestemt rekkefølge, og en indeks er plassnummeret til én av dem — det første elementet har indeks 0.

Løkke 1 — å bytte om på to verdier (~6 min)

To personer står i feil rekkefølge i en kø, og skal bytte plass. I virkeligheten går de rundt hverandre samtidig. I kode er ikke det like enkelt: skriver du «den første blir den andre» og deretter «den andre blir den første», har du allerede mistet den opprinnelige verdien til den første.

Alle sorteringsalgoritmer bygger på dette ene grepet. Får du byttet feil, blir hele sorteringen feil, så det er verdt seks minutter.

Bytteidiomet `a, b = b, a`

Python regner ut hele høyresida først, og tildeler så verdiene til navnene på venstresida. Derfor bytter a, b = b, a innholdet i to variabler i én linje, uten en hjelpevariabel.

Det virker like godt på to plasser i ei liste: x[0], x[1] = x[1], x[0] bytter de to første elementene. Dette er formen boka bruker overalt, og den formen sensor forventer å se i en boblesortering.

På plass (in place)

En operasjon skjer på plass — «in place» på engelsk — når den endrer objektet som allerede finnes, i stedet for å lage et nytt. Bytteidiomet endrer lista på plass: etterpå finnes det fortsatt bare én liste, men innholdet står i en annen rekkefølge.

Det motsatte er å bygge et nytt objekt og la originalen stå urørt. Skillet går igjen gjennom hele kapitlet, og er det som skiller x.sort() fra sorted(x).

✏️Eksempel 1: bytt to naboer i en rutetabell

Fire bussavganger er registrert som minutter etter midnatt, men de to første er skrevet inn i feil rekkefølge. Bytt om på dem, og skriv ut lista etterpå.

Ett grep, én linje:

tider = [312, 287, 401, 355]
tider[0], tider[1] = tider[1], tider[0]
print(tider)

Utskrift:

[287, 312, 401, 355]

Den naive framgangsmåten — først «gi den første verdien til den andre», så motsatt — ødelegger den ene verdien før den er tatt vare på:

a = 5
b = 9
a = b
b = a
print(a, b)

Utskrift:

9 9

Begge variablene endte på 9, fordi 5-tallet var borte allerede etter linje 3. Den formen skal du aldri skrive.

📝Oppgave 1

(Innstegsoppgave, sjanger B — kodesporing, altså «hva skriver dette programmet ut?».) Skriv utskriften nøyaktig slik terminalen viser den.

verdier = [5, 9, 2]
verdier[0], verdier[2] = verdier[2], verdier[0]
print(verdier)

Løkke 2 — boblesortering (~16 min)

Tenk deg at du holder ei liste med ventetider og bare får lov til å se på to naboer om gangen. Da finnes det én åpenbar strategi: gå gjennom lista fra venstre, og bytt hver gang venstre nabo er større enn høyre. Den største verdien blir dyttet med hele veien og ender bakerst — som en boble som stiger til overflaten. Det er hele ideen bak boblesortering.

Etter én slik gjennomgang er det største tallet garantert på plass. Etter to gjennomganger er de to største på plass. Derfor kan neste gjennomgang stoppe litt tidligere enn den forrige.

Boblesortering

En sorteringsalgoritme som bare sammenligner naboer: gå gjennom lista fra start til slutt, og bytt to naboer hver gang de står i feil rekkefølge. Gjenta gjennomgangen til hele lista er sortert.

Algoritmen sorterer på plass — den lager ingen ny liste. Den er enkel å skrive for hånd, og det er nettopp derfor den brukes på eksamen. Standardformen sorterer stigende; bytter du > med < i sammenligningen, sorterer den synkende.

Passering

Én passering er én full gjennomgang av lista med den indre løkka. Den ytre løkka teller passeringene.

Etter passering nummer i (talt fra 0) står de i + 1 største verdiene ferdig sortert bakerst. Derfor kan den indre løkka gå kortere for hver passering — det er det - i i range(len(x) - 1 - i) gjør. Ei liste med n elementer er ferdig etter n - 1 passeringer.

📜Kodemønster: boblesortering

Dette er mønsteret du skal kunne skrive fra bunnen, uten å slå opp. Blokken er et fragment — den kan ikke kjøres alene, fordi lista x må komme et sted fra. Den ferdige, kjørbare funksjonen står i eksempel 3 rett under.

for i in range(len(x) - 1):
    for j in range(len(x) - 1 - i):
        if x[j] > x[j + 1]:
            x[j], x[j + 1] = x[j + 1], x[j]

Fire linjer, og hver av dem har en grunn:

1. Ytre løkke range(len(x) - 1)n - 1 passeringer er nok. Er det siste elementet det eneste som gjenstår, er det allerede på plass.
2. Indre løkke range(len(x) - 1 - i)- 1 fordi du sammenligner x[j] med x[j + 1] og ikke vil indeksere utenfor lista, - i fordi halen allerede er sortert.
3. Sammenligningen x[j] > x[j + 1] — bytt bare når de står feil. Bruk < for synkende rekkefølge.
4. Byttet i én linje.

Mønsteret virker like godt på rader i en tabell: da sammenligner du x[j][k] > x[j + 1][k] for kolonnen k, og bytter hele radene.

✏️Eksempel 2: én passering, steg for steg

Ventetidene ved fire gjenvinningsstasjoner er [312, 287, 401, 355]. Kjør den indre løkka én gang, og vis lista etter hvert steg.

Den indre løkka går fra j = 0 til j = 2range(len(x) - 1) gir tre verdier når lista har fire elementer.

tider = [312, 287, 401, 355]
for j in range(len(tider) - 1):
    if tider[j] > tider[j + 1]:
        tider[j], tider[j + 1] = tider[j + 1], tider[j]
    print(j, tider)

Utskrift:

0 [287, 312, 401, 355]
1 [287, 312, 401, 355]
2 [287, 312, 355, 401]

Sporingstavle for den samme passeringen:

jSammenlignerBytte?Lista etter steget
0312 > 287ja[287, 312, 401, 355]
1312 > 401nei[287, 312, 401, 355]
2401 > 355ja[287, 312, 355, 401]

Legg merke til at 401 — den største verdien — er dyttet helt bakerst etter én passering. Det er garantien boblesortering hviler på.

✏️Eksempel 3: hele boblesorteringen

Skriv boblesorter(x) som sorterer ei liste med tall stigende, og vis at lista er endret også utenfor funksjonen.

Funksjonen er de fire linjene fra mønsteret, pluss return:

def boblesorter(x):
    for i in range(len(x) - 1):
        for j in range(len(x) - 1 - i):
            if x[j] > x[j + 1]:
                x[j], x[j + 1] = x[j + 1], x[j]
    return x

tider = [312, 287, 401, 355, 298]
print(boblesorter(tider))
print(tider)

Utskrift:

[287, 298, 312, 355, 401]
[287, 298, 312, 355, 401]

Begge linjene er like, og det er ikke en trykkfeil: funksjonen sorterer lista på plass, så tider er endret utenfor funksjonen også. return x er derfor strengt tatt overflødig, men den gjør funksjonen behagelig å bruke — og sensor trekker ikke for den.

Sporingstavle, én rad per passering:

Passering iIndre løkke j gårBytterLista etter passeringen
00 til 33[287, 312, 355, 298, 401]
10 til 21[287, 312, 298, 355, 401]
20 til 11[287, 298, 312, 355, 401]
30 til 00[287, 298, 312, 355, 401]

Legg merke til at siste passering ikke gjorde noe bytte. Lista var ferdig sortert allerede etter passering 2 — algoritmen vet det bare ikke, og går løpet ut.
Flere løsninger er riktige. Noen skriver den ytre løkka som range(len(x)) og lar den gå én runde for mye; det gir samme resultat og full pott. Andre bruker en while-løkke som stopper når en passering ikke gjorde noen bytter. Alle tre er gyldige.

📝Oppgave 2
Sjanger B

Hva skriver programmet ut? Bare den indre løkka kjøres her — altså én passering.

x = [8, 3, 5, 1]
for j in range(len(x) - 1):
    if x[j] > x[j + 1]:
        x[j], x[j + 1] = x[j + 1], x[j]
print(x)

📝Oppgave 3
Eksamensnivå, sjanger G

I en treningslogg står antall minutter per økt. Skriv sorter_synkende(x) som sorterer lista med boblesortering slik at den lengste økta står først. Funksjonen skal endre lista på plass og returnere den.

Test den på [45, 70, 30, 70, 55].

Løkke 3 — snarveiene .sort() og sorted() (~10 min)

I praksis skriver ingen boblesortering for å sortere ei liste. Python har sortering innebygd, og — dette er viktig i akkurat dette emnet — de offisielle løsningsforslagene bruker den fritt. Du taper ingenting på å bruke snarveien der oppgaven ikke uttrykkelig ber om boblesortering.

Det finnes to former, og forskjellen mellom dem er den vanligste kodesporingsfella i hele kapitlet.

`x.sort()`

Sorterer lista x på plass, stigende. Metoden returnerer None — ikke lista.

Det betyr at x = x.sort() ødelegger lista di: x peker etterpå på None. Riktig bruk er x.sort() alene på en linje, og så bruke x videre. Etter kallet er den opprinnelige rekkefølgen tapt.

`sorted(x)`

Returnerer en ny, sortert liste. Originalen x står urørt, og du må ta vare på resultatet: ny = sorted(x).

Dette er formen du vil ha når du trenger begge rekkefølgene, eller når du sorterer noe du fikk inn som parameter og ikke vil endre for den som kalte deg. sorted virker også på ting som ikke er lister — for eksempel gir sorted('bad') lista ['a', 'b', 'd'].

`reverse=True`

Snur sorteringsretningen til synkende. Den fungerer i begge former: x.sort(reverse=True) og sorted(x, reverse=True).

Dette er raskere og tryggere enn å sortere stigende og deretter snu med x.reverse() — og det er lettere å lese for sensor. Merk at reverse er et navngitt argument: sorted(x, True) er ikke det samme og gir feil.

✏️Eksempel 4: de to formene side om side

Vis forskjellen på sorted(x) og x.sort() på den samme lista med ventetider, og hva x.sort() faktisk gir tilbake.

Fire linjer er nok til å se hele forskjellen:

tider = [312, 287, 401, 355, 298]
ny = sorted(tider)
print(ny)
print(tider)
tider.sort()
print(tider)
print(tider.sort())

Utskrift:

[287, 298, 312, 355, 401]
[312, 287, 401, 355, 298]
[287, 298, 312, 355, 401]
None

Linje for linje: sorted ga en ny sortert liste, og originalen sto fortsatt i sin egen rekkefølge. Så endret .sort() originalen. Til slutt viser den fjerde utskriften hva metoden returnerer — None.

Begge gir full pott. En fasit som bruker sorted(...) og en som bruker boblesortering, vurderes likt i dette emnet. Velg sorted når oppgaven bare vil ha resultatet, og skriv boblesorteringen når oppgaven ber om «en sorteringsalgoritme» eller når du skal forklare hvordan sortering virker.

`min(x)` og `max(x)` — når du ikke trenger å sortere

Trenger du bare den minste eller største verdien, er sortering unødvendig arbeid: min(x) og max(x) gir den direkte, og de leser bedre.

Sorter når du trenger rekkefølgen — de tre beste, eller hele lista rangert. Bruk min/max når du bare trenger én verdi. Merk at begge krasjer med ValueError på ei tom liste, og at ingen av dem sier hvor i lista verdien sto; til det trenger du x.index(...) eller en egen løkke.

📝Oppgave 4
Eksamensnivå, sjanger B

Hva skriver programmet ut? Skriv alle tre linjene nøyaktig.

maalinger = [4, 1, 7]
resultat = maalinger.sort()
print(resultat)
print(maalinger)
print(sorted([4, 1, 7], reverse=True))

Løkke 4 — rangér radene i en tabell (~18 min)

Dette er formen eksamen faktisk spør om. Du har lest en fil inn i en 2D-liste — en tabell der hver rad selv er ei liste — og skal levere radene sortert etter én bestemt kolonne.

To ting gjør oppgaven vanskeligere enn å sortere ei liste med tall. For det første må du sammenligne én kolonne i raden, ikke hele raden. For det andre skal du ikke anta at kolonnen står på en bestemt plass: den som får full pott, finner kolonnenummeret fra overskriftsraden i stedet for å skrive et tall rett inn i koden.

`tabell[0].index(navn)` — dynamisk kolonneindeks

Overskriftsraden tabell[0] er ei liste med kolonnenavn. .index(navn) gir plassnummeret til navnet i den lista — altså kolonnenummeret du skal bruke i resten av funksjonen.

Eksempel: k = tabell[0].index('pris') gir 2 hvis overskriftsraden er ['butikk', 'vare', 'pris']. Dette er et uttalt fullscore-krav i emnet (feilkode #4 er å hardkode kolonnetallet): flytter noen på kolonnene i fila, virker koden din fortsatt. .index gir ValueError hvis navnet ikke finnes.

`key`-parameteren
sorted(x, key=f) sorterer ikke etter elementene selv, men etter det f gir for hvert element. Elementene flyttes samlet — bare rekkefølgen bestemmes av nøkkelen.

Den fungerer likt i begge former: x.sort(key=f) og sorted(x, key=f). Du kan kombinere den med retningen: sorted(x, key=f, reverse=True). Uten key sammenlignes elementene direkte, og for lister betyr det at første element avgjør, deretter det andre, og så videre.

`lambda rad: rad[k]`

En lambda er en navnløs funksjon skrevet på én linje: etter kolonet står uttrykket som returneres. lambda rad: rad[k] betyr «gitt en rad, gi meg element nummer k i den».

Det er nøyaktig det key trenger for å sortere en tabell på en kolonne: sorted(rader, key=lambda rad: rad[k]). Du kan skrive det samme som en vanlig funksjon med def og sende funksjonsnavnet inn — begge deler er riktig, og lambdaen er bare kortere.

📜Kodemønster: rangér en tabell på en kolonne

Fire steg, i denne rekkefølgen:

1. Finn kolonnen dynamisk: k = tabell[0].index('ventetid').
2. Skill overskriftsraden fra dataene: rader = tabell[1:]. Overskriften skal ikke være med i sorteringen — den ville havnet et vilkårlig sted.
3. Sorter: sortert = sorted(rader, key=lambda rad: rad[k]), eller boblesortering der du sammenligner rader[j][k] > rader[j + 1][k] og bytter hele rader.
4. Returner: enten bare radene, eller overskriften limt på igjen med [tabell[0]] + sortert. Les oppgaveteksten — den sier hva som skal med.

Trenger du bare de beste, tar du et utsnitt til slutt: sortert[:3].

Har oppgaven utlevert en ferdig hjelpefunksjon, typisk kalt sort_list(tabell, k), hopper du over steg 3 og kaller den i stedet. Da er poenget å vise at du sender inn riktig k og behandler resultatet riktig.

`sortert[:n]` — topp-N

Et utsnitt av de n første elementene i ei ferdig sortert liste. Sluttgrensa er eksklusiv, så sortert[:3] gir tre rader: indeks 0, 1 og 2.

Utsnittet gir alltid ei ny liste, så originalen står urørt. Er lista kortere enn n, får du bare det som finnes — [1, 2][:5] gir [1, 2] uten feilmelding. Det gjør formen trygg også på tomme og korte tabeller.

Stabil sortering

En sortering er stabil når elementer med lik nøkkel beholder den innbyrdes rekkefølgen de hadde før sorteringen.

Pythons sort() og sorted() er stabile. Det betyr at hvis to gjenvinningsstasjoner begge har ventetid 6, kommer den som sto først i fila, først også etterpå. Boblesorteringen i dette kapitlet er også stabil, fordi den bare bytter når venstre nabo er strengt større enn høyre — bytter du > med >=, mister du stabiliteten.

`sort_list(tabell, k)` — den utleverte hjelpefunksjonen

På noen eksamenssett får du en ferdig sorteringsfunksjon oppgitt i oppgaveteksten, typisk med signaturen sort_list(tabell, k): den returnerer radene sortert stigende på kolonne nummer k.

Send inn radene UTEN overskriftsraden — altså sort_list(tabell[1:], k). Er overskriften med, sammenlignes 'pris' med et tall, og du får TypeError: '>' not supported between instances of 'str' and 'int'.

Da skal du ikke skrive sorteringen selv. Poenget er å vise at du finner riktig k, kaller funksjonen med riktige argumenter og bruker resultatet videre. Rangering med utlevert funksjon drilles i kap. 7.5. Les alltid oppgaveteksten for om en slik funksjon er gitt før du bruker tid på å skrive en sortering fra bunnen.

✏️Eksempel 5: rangér gjenvinningsstasjoner etter ventetid

Tabellen under har en overskriftsrad og fire datarader. Skriv en funksjon som gir radene sortert stigende på kolonnen ventetid, uten å anta hvor den kolonnen står. Løs den både med snarveien og med boblesortering.

Med snarveien, som er formen de offisielle løsningsforslagene bruker:

tabell = [['stasjon', 'ventetid', 'apen'],
          ['Heggstad', 14, 'ja'],
          ['Sluppen', 6, 'ja'],
          ['Ranheim', 22, 'nei'],
          ['Tiller', 6, 'ja']]

def rangert_pa(tabell, kolonnenavn):
    k = tabell[0].index(kolonnenavn)
    rader = tabell[1:]
    return sorted(rader, key=lambda rad: rad[k])

for rad in rangert_pa(tabell, 'ventetid'):
    print(rad)

Utskrift:

['Sluppen', 6, 'ja']
['Tiller', 6, 'ja']
['Heggstad', 14, 'ja']
['Ranheim', 22, 'nei']

Sluppen kommer før Tiller selv om begge har ventetid 6 — sorteringen er stabil, så de beholder rekkefølgen fra tabellen.

Med boblesortering, der hele rader byttes:

tabell = [['stasjon', 'ventetid', 'apen'],
          ['Heggstad', 14, 'ja'],
          ['Sluppen', 6, 'ja'],
          ['Ranheim', 22, 'nei'],
          ['Tiller', 6, 'ja']]

def rangert_boble(tabell, kolonnenavn):
    k = tabell[0].index(kolonnenavn)
    rader = tabell[1:]
    for i in range(len(rader) - 1):
        for j in range(len(rader) - 1 - i):
            if rader[j][k] > rader[j + 1][k]:
                rader[j], rader[j + 1] = rader[j + 1], rader[j]
    return rader

for rad in rangert_boble(tabell, 'ventetid'):
    print(rad)

Utskrift:

['Sluppen', 6, 'ja']
['Tiller', 6, 'ja']
['Heggstad', 14, 'ja']
['Ranheim', 22, 'nei']

Samme resultat, og begge gir full pott. Legg merke til de to grepene som er felles: kolonnenummeret hentes fra overskriftsraden, og overskriften holdes utenfor sorteringen med tabell[1:].

En margnote om uttelling: sensor belønner den overordnede strukturen. Har du funnet kolonnen dynamisk, skilt ut overskriften og sortert på riktig felt, får du god uttelling selv om du skulle bomme med én på en løkkegrense.

Leksikografisk sortering av tekst

Strenger sorteres tegn for tegn, ikke etter tallverdi. Derfor kommer '10' før '9': første tegn '1' er mindre enn '9', og da er saken avgjort.

Dette rammer deg hver gang du har glemt int() etter innlesing fra fil eller input() — feilkode #1. Symptomet er en sortering som ser tilfeldig ut, uten noen feilmelding. Merk også at store bokstaver kommer før små i denne ordningen: 'Ås' sorteres foran 'ape'.

✏️Eksempel 6: når sorteringen ser gal ut

En tabell er lest inn fra fil, men tallkolonnen ble aldri konvertert. Vis hva sorteringen gir da, og hva den gir når int() er på plass.

Samme verdier, to datatyper:

tekst = ['9', '10', '7', '100']
tall = [9, 10, 7, 100]
print(sorted(tekst))
print(sorted(tall))

Utskrift:

['10', '100', '7', '9']
[7, 9, 10, 100]

Den første rekkefølgen er ikke tilfeldig — den er alfabetisk. '100' kommer før '7' fordi '1' kommer før '7'.

Feilen skjer nesten alltid ved innlesing: linje.strip().split(';') gir bare strenger, uansett hva som står i fila. Konverteringen må du gjøre selv, med int(felt[2]) eller float(felt[2]), mens du bygger tabellen.

📝Oppgave 5
Sjanger B

En tabell med strømpriser er sortert på feil måte. Hva skriver programmet ut?

priser = [['NO1', '52'], ['NO3', '9'], ['NO4', '117']]
k = 1
print(sorted(priser, key=lambda rad: rad[k]))

📝Oppgave 6
Eksamensnivå, sjanger G

Et bibliotek har utlånstallene for året i tabellen utlan, med overskriftsraden ['tittel', 'utlan', 'avdeling'].

Skriv rangert_etter_utlan(tabell) som returnerer radene — uten overskriftsraden — sortert synkende på utlånstallet, altså den mest utlånte boka først.

a) Løs den med boblesortering.
b) Løs den med sorted og en key.
c) Utvid b) slik at funksjonen tar et ekstra argument n og bare returnerer de n mest utlånte. Funksjonen skal ikke krasje om tabellen har færre enn n datarader.

📝Oppgave 7
Eksamensnivå, sjanger G

Værstasjonene i tabellen maalinger har overskriftsraden ['stasjon', 'nedbor', 'fylke'].

a) Skriv sorter_stabilt(tabell) som returnerer dataradene sortert stigende på nedbør, og forklar i én setning hva som skjer med to stasjoner som har samme nedbørmengde.
b) Skriv torreste(tabell) som returnerer navnet på stasjonen med minst nedbør, uten å sortere i det hele tatt. Returner None hvis tabellen ikke har datarader.

📝Oppgave 8
Sjanger C

Skriv én presis setning om hva denne funksjonen oppnår. Setningen skal si hva den gir, ikke hvordan den regner.

def ukjent(tabell, navn):
    k = tabell[0].index(navn)
    rader = tabell[1:]
    sortert = sorted(rader, key=lambda rad: rad[k], reverse=True)
    return sortert[:3]

Repetisjon — de seks setningene du bør ha med deg
API- og konstruksjonsliste

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.