SimReal - Sortering - Boblesortering

Vi ønsker å sortere en tallmengde i stigende rekkefølge.
Hvis tallmengden er stor, kan det være hensiktsmessig med en klar strategi for denne sorteringen, spesielt mht en eventuell maskinell sorteringsbehandling.
På denne siden vises et eksempel på en slik sorterings-strategi, den såkalte 'boblesorteringen'.

Som eksempel på boblesortering tenker vi oss den usorterte tallmengden bestående av tallene
9-3-5-7-2.
Disse tallene ønsker vi å sortere i stigende rekkefølge. Vi starter med de to første tallene 9 og 3.
Disse to tallene er plassert i gal rekkefølge i forhold til hverandre, og vi bytter derfor rekkefølgen på disse to tallene.
Tallfølgen bli nå derfor: 3-9-5-7-2.

Vi sammenligner så tallene nr 2 og 3, dvs tallene 9 og 5.
Disse er også plassert i gal rekkefølge, og vi bytter om til 3-5-9-7-2.
Tall nr 3 og 4 er plassert i gal rekkefølge, vi bytter om til 3-5-7-9-2.
Tall nr 4 og 5 er plassert i gal rekkefølge, vi bytter om til 3-5-7-2-9.
Det største tallet (her 9) er nå korrekt plassert.

Vi starter nå forfra igjen.
Tall nr 1 og 2 (her 3 og 5) er korrekt plassert, ingen ombytting.
Tall nr 2 og 3 (her 5 og 7) er korrekt plassert, ingen ombytting.
Tall nr 3 og 4 (her 7 og 2) er galt plassert, ombytting til 3-5-2-7-9.
De to største tallene er nå korrekt plassert.

Vi starter forfra igjen.
Tall nr 1 og 2 (her 3 og 5) er korrekt plassert, ingen ombytting.
Tall nr 2 og 3 (her 5 og 2) er galt plassert, ombytting til 3-2-5-7-9.
De tre største tallene er nå korrekt plassert.

Vi starter forfra igjen.
Tall nr 1 og 2 (her 3 og 2) er galt plassert, ombytting til 2-3-5-7-9.
Tall nr 2 og 3 (her 5 og 2) er galt plassert, ombytting til 3-2-5-7-9.
De fire største tallene (og dermed også det femte) er nå korrekt plassert.

Her vises en algoritme for boble-sortering.
tab er tabellen som inneholder tallene som skal sorteres.
n er antall tall i tabellen.
Algoritmen inneholder to hoved-sløyfer:
Den innerste sløyfen (for-sløyfe) gjennomløper tabellen for å få et nytt tall plassert korrekt mot slutten av tabellen.
Merk at denne sløyfen gjennomløpes en gang mindre for hver gang (opp til n-j) svarende til at stadig nye tall blir plassert korrekt mot slutten av tabellen.
Den ytterste sløyfen (while-sløyfe) sørger for at tabell-gjennomløpingen kan starte forfra igjen.

Den innerste sløyfen er en for-sløyfe siden vi ved inngangen til denne sløyfen alltid vet hvor mange gjennomløp denn sløyfen trenger.

Den ytterste sløyfen er en while-sløyfe for å hindre at vi for mange ganger starter for-sløyfe-gjennomgangen på nytt. Det kan jo tenkes at tabellen plutselig viser seg å være sortert, denne testen ivaretas av en boolsk variabel bytt.