Indholdsfortegnelse:
Definition - Hvad betyder Bubble Sort?
Bubble sort er en sorteringsalgoritme, der fungerer ved gentagne gange at gennemgå lister, der skal sorteres, sammenligne hvert par tilstødende elementer og bytte dem, hvis de er i forkert rækkefølge. Denne godkendelsesprocedure gentages, indtil der ikke kræves nogen swaps, hvilket indikerer at listen er sorteret. Bobelsortering får sit navn, fordi mindre elementer boble mod toppen af listen.
Boblesorter omtales også som synkende sortering eller sammenligningssortering.
Techopedia forklarer Bubble Sort
Boblesortering har en worst-case og gennemsnitlig kompleksitet O (n2), hvor n er antallet af sorterede poster. I modsætning til de andre sorteringsalgoritmer, registrerer boblesortering, om den sorterede liste er effektivt indbygget i algoritmen. Boblesorteringsevne over en allerede sorteret liste er O (n).
Elementernes placering i boblesortering spiller en vigtig rolle i bestemmelsen af ydeevnen. Store elementer i starten udgør ikke et problem, da de let kan udskiftes. De små elementer mod slutningen bevæger sig langsomt til begyndelsen. Som sådan kaldes disse elementer kaniner og skildpadder.
Boblesorteringsalgoritmen kan optimeres ved at placere større elementer i den endelige position. Efter hver gennemgang sorteres alle elementer efter den sidste swap og behøver ikke at kontrolleres igen, hvorved man springer over sporing af udvekslede variabler.
