Boblesortering

Boblesortering er en algoritme som brukes til å sortere en liste med elementer i stigende eller synkende rekkefølge. Algoritmen er basert på en sammenligning mellom par av elementer i listen for å bytte deres plass dersom de er i feil rekkefølge. Ved å gjenta denne prosessen flere ganger, flytter boblesorteringen gradvis de største (eller minste) elementene mot slutten (eller begynnelsen) av listen.

Algoritme

Boblesortering fungerer ved å iterere gjennom listen og sammenligne hvert par av påfølgende elementer. Hvis de to elementene er i feil rekkefølge, bytter algoritmen plass på dem. Denne prosessen fortsetter til slutten av listen er nådd. Ved første iterasjon er det garantert at det største elementet er plassert på riktig sted i listen. Deretter gjentas prosessen for de gjenværende elementene, med unntak av det siste elementet som allerede er sortert, og slik fortsetter man til hele listen er sortert.

Pseudokode

function boblesortering(liste)
    n = lengden av listen
    gjenta n-1 ganger
        for i = 0 til n-2
            hvis liste[i] > liste[i+1]
                bytt plass på liste[i] og liste[i+1]
            slutt hvis
        slutt for
    slutt gjenta
slutt funksjon

Kompleksitet

Boblesortering er en enkel algoritme å implementere, men den har en relativt høy tidskompleksitet sammenlignet med mer avanserte sorteringsalgoritmer. Den har en gjennomsnittlig og verste fall-tidskompleksitet på O(n^2), der n er antall elementer i listen. Dette gjør boblesortering ineffektiv for store mengder data.

Til tross for sin høye tidskompleksitet, har boblesortering noen bruksområder i spesielle tilfeller. Algoritmen er spesielt nyttig når listen som skal sorteres er nesten sortert eller allerede sortert. I slike tilfeller kan boblesortering være en enkel og effektiv løsning.