Innholdsfortegnelse:
Definisjon - Hva betyr Bubble Sort?
Boble sortering er en sorteringsalgoritme som fungerer ved å gjentatte ganger gå gjennom lister som må sorteres, sammenligne hvert par tilstøtende elementer og bytte dem hvis de er i feil rekkefølge. Denne passeringsprosedyren gjentas til det ikke er behov for noen bytter, noe som indikerer at listen er sortert. Bubble sort får navnet sitt fordi mindre elementer boble mot toppen av listen.
Boble sortering er også referert til som synkende sortering eller sammenligning sortering.
Techopedia forklarer Bubble Sort
Boble sortering har en worst-case og gjennomsnittlig kompleksitet på O (n2), der n er antall sorterte elementer. I motsetning til de andre sorteringsalgoritmene, oppdager boblesortering om den sorterte listen effektivt er innebygd i algoritmen. Boblesorteringsytelse over en allerede sortert liste er O (n).
Elementenes plassering i boble sorterer en viktig rolle i å bestemme ytelsen. Store elementer i begynnelsen utgjør ikke et problem da de enkelt byttes. De små elementene mot slutten beveger seg sakte til begynnelsen. Som sådan kalles disse elementene kaniner og skilpadder.
Bubblesorteringsalgoritmen kan optimaliseres ved å plassere større elementer i sluttposisjonen. Etter hver passering blir alle elementene etter siste bytte sortert og trenger ikke å sjekkes på nytt, og derved hopper du over sporing av utvekslede variabler.
