Boblesortering
Boblesortering er den sorteringsalgoritme, der er nemmest at forklare: sammenlign to naboer, byt dem, hvis de står i forkert rækkefølge, og gentag. Den er langsom på lange lister, men hvert trin er let at følge, og derfor er den den klassiske første algoritme at se på.
Idéen
Gå gennem listen fra venstre mod højre, og se på hvert par naboer. Hvis den venstre værdi er større end den højre, så byt dem. Når du når enden, er den største værdi blevet ført helt hen på sidste plads, ligesom en boble stiger op til overfladen. Sådan en tur kaldes et gennemløb. Gentag gennemløbene, til listen er sorteret.
Et eksempel
Tag 5, 1, 4, 2, 8. Første gennemløb sammenligner 5 og 1 og bytter dem, derefter 5 og 4 (byt), 5 og 2 (byt) og 5 og 8 (ingen ombytning): 1, 4, 2, 5, 8. 8-tallet står nu på sin endelige plads. Andet gennemløb sammenligner 1 og 4 (ingen ombytning), 4 og 2 (byt) og 4 og 5 (ingen ombytning): 1, 2, 4, 5, 8. Tredje gennemløb bytter slet ikke noget, så listen er sorteret: 9 sammenligninger og 4 ombytninger.
Hvorfor hvert gennemløb sætter én værdi mere på plads
Under et gennemløb bliver den hidtil største værdi altid ført med: Når gennemløbet når den, flytter hver sammenligning den én plads længere til højre. Første gennemløb sætter altså den største værdi sidst, andet gennemløb den næststørste lige før den, og så videre. Efter gennemløb k ligger de sidste k pladser fast, og næste gennemløb kan stoppe én plads tidligere. Derfor bliver gennemløbene kortere.
Ombytninger svarer til inversioner
En inversion er et par værdier i forkert rækkefølge: en større værdi et sted før en mindre. At bytte to naboer, der står forkert, fjerner præcis én inversion og skaber ingen. Boblesortering laver derfor præcis lige så mange ombytninger, som startlisten har inversioner, uanset i hvilken rækkefølge sammenligningerne kommer. En sorteret liste har ingen; en omvendt liste med n værdier har n(n − 1)/2, det højst mulige.
Tidligt stop og prisen
Hvis et helt gennemløb ikke bytter noget, står alle naboer i rækkefølge, og listen er sorteret. Ved at tjekke for det kan boblesortering gøre en sorteret liste færdig i ét gennemløb med n − 1 sammenligninger. I værste fald kræver den stadig n − 1 gennemløb og n(n − 1)/2 sammenligninger, og i gennemsnit er antallet af ombytninger n(n − 1)/4. Begge vokser med n², så en dobbelt så lang liste tager omkring fire gange så lang tid.
Boblesortering er stabil: Lige store værdier bytter aldrig, så de beholder deres rækkefølge. Den sorterer på stedet uden ekstra hukommelse. Indsættelsessortering har de samme egenskaber og kræver som regel færre trin, og flettesortering og quicksort bruger tid proportional med n log n, hvilket er langt mindre på lange lister.
Udforsk den
Åbn appen og tryk på Afspil, eller tryk på Trin for at gå én sammenligning ad gangen. De to værdier, der sammenlignes, er fremhævet, en ombytning vises i sin egen farve, og værdier, der allerede står på plads, bliver grønne. Prøv en omvendt liste for at se det værste tilfælde, en næsten sorteret liste for at se tidligt stop afslutte sorteringen efter få gennemløb, eller skriv tallene fra eksemplet ovenfor.
Ofte stillede spørgsmål
Hvad er tidskompleksiteten for boblesortering?
O(n²) i værste og gennemsnitlige tilfælde: op til n(n − 1)/2 sammenligninger for n værdier. Med tidligt stop tager en allerede sorteret liste O(n), ét gennemløb. Den kræver kun O(1) ekstra hukommelse.
Er boblesortering stabil?
Ja. Den bytter kun to naboer, når den venstre er strengt større, så lige store værdier passerer aldrig hinanden og beholder deres oprindelige rækkefølge.
Hvad er forskellen på boblesortering og indsættelsessortering?
Begge bytter naboer, og begge laver lige så mange ombytninger, som der er inversioner. Boblesortering laver hele gennemløb over den usorterede del; indsættelsessortering skubber hver ny værdi kun så langt tilbage, som den skal, så den laver som regel færre sammenligninger, især på næsten sorterede lister.
Hvornår er boblesortering et godt valg?
Mest i undervisning og til meget korte lister, hvor enkelhed betyder mere end hastighed. Til alt større er den indbyggede sortering i dit programmeringssprog langt hurtigere.
Er du klar til at prøve?
Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.
Prøv boblesortering