Bubble Sort vs Selection Sort
Bubble sort er en sorteringsalgoritme, der fungerer ved at gå gennem listen for at blive sorteret gentagne gange, mens par af elementer, der er tilstødende, sammenlignes. Hvis et par elementer er i den forkerte rækkefølge, ombyttes de for at placere dem i den rigtige rækkefølge. Denne gennemgang gentages, indtil der ikke er behov for yderligere ombytning. Udvælgelsessortering er også en sorteringsalgoritme, som starter med at finde minimumselementet i listen og bytte det med det første element. Denne proces gentages for resten af listen ved at placere ombyttede elementer i rækkefølge.
Hvad er Bubble Sort?
Bubble sort er en sorteringsalgoritme, der fungerer ved at gå gennem listen for at blive sorteret gentagne gange, mens par af elementer, der er tilstødende, sammenlignes. Hvis et par elementer er i den forkerte rækkefølge, ombyttes de for at placere dem i den rigtige rækkefølge. Denne gennemgang gentages, indtil der ikke kræves yderligere ombytning (hvilket betyder, at listen er sorteret). Da de mindre elementer i listen kommer til tops efterhånden som en boble kommer til overfladen, får den navnet bubble sort. Boblesortering er en meget simpel sorteringsalgoritme, men den har en gennemsnitlig sagstidskompleksitet på O(n2), når man sorterer en liste med n elementer. På grund af dette er boblesortering ikke egnet til sortering af lister med et stort antal elementer. Men på grund af sin enkelhed undervises der i boblesortering under introduktioner til algoritmer.
Hvad er udvalgssortering?
Selection sort er også en anden sorteringsalgoritme, der starter med at finde minimumselementet på listen og bytte det med det første element. Derefter findes minimumselementet fra resten af listen (fra det andet element til det sidste element på listen) og ombyttes med det andet element. Denne proces gentages for resten af listen ved at placere ombyttede elementer i rækkefølge. Så i udvælgelsessortering, på ethvert trin af algoritmen, er listen opdelt i to dele, hvor den ene del indeholder sorterede elementer, og den anden del indeholder usorterede elementer. Efterhånden som algoritmen skrider frem, vokser den sorterede liste fra venstre mod højre. Udvælgelsessortering har også en gennemsnitlig sagstidskompleksitet på O(n2). Derfor er den heller ikke egnet til at sortere store lister.
Hvad er forskellen mellem boblesortering og udvalgssortering?
Selv om både boblesorterings- og udvælgelsesorteringsalgoritmerne har en gennemsnitlig sagstidskompleksitet på O(n2), er boblesortering næsten altid bedre end udvælgelsessortering. Dette skyldes antallet af swaps, der er nødvendige af de to algoritmer (boblesortering kræver flere swaps). Men på grund af enkeltheden ved boblesortering er dens kodestørrelse meget lille. Stabilitet er en anden forskel i disse to algoritmer. En stabil sorteringsalgoritme er en sorteringsalgoritme, der bevarer rækkefølgen af poster, hvis listen indeholder elementer med samme værdi. I den forstand er udvælgelsessortering ikke en stabil algoritme, mens boblesortering er en stabil algoritme.
