Boblesortering i pseudokode
Lov på eksamen
- Datamaskin med programmeringsverktøy
- Lærebok, dokumentasjon og egne notater og programmer
Ikke åpent internett (bare noen utvalgte nettressurser), kommunikasjon med andre eller kunstig intelligens.
Kan den løses uten PC?
2 av 3 deloppgaver kan løses uten PC.
Fra 2027 er det bare kalkulator og skriftlige hjelpemidler på del 2. Vurderingen er gjort med KI og kan inneholde feil.
Elementene i en indeksert variabel (liste/array) skal sorteres i stigende rekkefølge etter følgende algoritme: Man sammenligner hvert element fra venstre til høyre i listen med neste element, og hvis elementet er større enn neste element, bytter de plass. Deretter går man videre til neste element og sammenligner på nytt frem til hele listen er gjennomgått. Dette gjentas til hele listen gjennomgås uten at det forekommer noen ombyttinger.
Under finner du deler av pseudokoden for denne algoritmen. Her er a en liste med n elementer, og a[i] er elementet på plass i i listen.
SET i TO 0
FOR hver i LESSER THAN n - 1
IF a[i] GREATER THAN a[i+1]
CALL byttPlass()
ENDIF
ENDFORPresisering: byttPlass() er en funksjon som bytter plass på to naboelementer i listen.
Hva blir innholdet i listen etter at vi har kjørt programmet representert ved pseudokoden over for listen a = [8, 5, 2, 6, 12], som har n = 5 elementer?
Utvid pseudokoden slik at programmet den representerer, sorterer ferdig listen a i stigende rekkefølge etter algoritmen som er vist øverst. Forklar endringene du gjør. Obs! Du må også lage pseudokode for funksjonen byttPlass().
Implementer pseudokoden fra punkt b i ditt programmeringsspråk. Listen skal leses inn automatisk, og den ferdig sorterte listen skal skrives til konsollet eller vises i programmet.
Fasit
[5, 2, 6, 8, 12]
En ytre løkke (REPEAT … UNTIL) gjentar gjennomgangen til en hel runde går uten ombyttinger. Et flagg byttet settes til FALSE ved starten av hver runde og til TRUE ved hver ombytting. byttPlass(a, i) bytter a[i] og a[i+1] ved hjelp av en hjelpevariabel.
LøsningsforslagKI-generert
Pseudokoden går gjennom listen én gang og sammenligner hvert element med naboen til høyre:
i | Sammenligning | Bytte? | Listen etterpå |
|---|---|---|---|
| 0 | 8 > 5 | ja | [5, 8, 2, 6, 12] |
| 1 | 8 > 2 | ja | [5, 2, 8, 6, 12] |
| 2 | 8 > 6 | ja | [5, 2, 6, 8, 12] |
| 3 | 8 > 12 | nei | [5, 2, 6, 8, 12] |
Etter én gjennomgang er listen [5, 2, 6, 8, 12]. Det største tallet som ikke står på riktig plass, «bobler» mot høyre, men listen er ikke ferdig sortert, siden 5 og 2 står i feil rekkefølge.
Algoritmen sier at gjennomgangen skal gjentas til en hel gjennomgang skjer uten ombyttinger. Vi trenger derfor
- en ytre løkke som gjentar gjennomgangen
- en variabel
byttetsom husker om det har skjedd en ombytting i denne runden - en funksjon
byttPlass()som vet hvilke elementer den skal bytte
FUNCTION byttPlass(a, i)
SET temp TO a[i]
SET a[i] TO a[i+1]
SET a[i+1] TO temp
ENDFUNCTION
REPEAT
SET byttet TO FALSE
SET i TO 0
FOR hver i LESSER THAN n - 1
IF a[i] GREATER THAN a[i+1]
CALL byttPlass(a, i)
SET byttet TO TRUE
ENDIF
ENDFOR
UNTIL byttet EQUAL TO FALSE
DISPLAY aForklaring av endringene:
- Ytre løkke. Den opprinnelige for-løkken er én gjennomgang. Den er lagt inne i en
REPEAT … UNTIL-løkke. Vi må alltid gjennom listen minst én gang for å vite om den er sortert, og derfor passerREPEAT … UNTIL, som sjekker betingelsen til slutt. EnWHILE byttet EQUAL TO TRUE-løkke virker også hvisbyttetsettes tilTRUEfør løkken. - Flagget
byttet. Det settes tilFALSEved starten av hver gjennomgang og tilTRUEhver gang to elementer bytter plass. Er det fortsattFALSEetter en hel gjennomgang, er listen sortert, og løkken stopper. - Funksjonen
byttPlass(a, i). Funksjonen må vite hvilken liste og hvilken plass den skal jobbe med. Derfor får denaogisom parametere. Vi trenger en hjelpevariabeltemp. Uten den ville vi overskreveta[i]før verdien var flyttet tila[i+1].
For listen i a) blir gjennomgangene:
| Gjennomgang | Listen etterpå | byttet |
|---|---|---|
| 1 | [5, 2, 6, 8, 12] | TRUE |
| 2 | [2, 5, 6, 8, 12] | TRUE |
| 3 | [2, 5, 6, 8, 12] | FALSE |
Etter tredje gjennomgang har det ikke skjedd noen ombytting, så programmet stopper og viser den sorterte listen.
Mulig forbedring: Etter hver gjennomgang står det største av de usorterte tallene på riktig plass bakerst. Den indre løkken kan derfor stoppe ett element tidligere for hver gjennomgang. Det er ikke nødvendig for at algoritmen skal virke.