Bubble Sort vs Insertion 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. Indsættelsessortering er også en sorteringsalgoritme, som fungerer ved at indsætte et element i inputlisten til den korrekte position i en liste, der allerede er sorteret. Denne proces anvendes gentagne gange, indtil listen er sorteret.
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 indsættelsessortering?
Indsættelsessortering er en anden sorteringsalgoritme, som fungerer ved at indsætte et element i inputlisten til den korrekte position i en liste (der allerede er sorteret). Denne proces anvendes gentagne gange, indtil listen er sorteret. Ved indsættelsessortering udføres sorteringen på stedet. Derfor vil de første i+1-poster på listen efter iterationen af algoritmen blive sorteret, og resten af listen vil være usorteret. Ved hver iteration vil det første element i den usorterede del af listen blive taget og indsat på det rigtige sted i den sorterede del af listen. Indsættelsessortering har en gennemsnitlig sagstidskompleksitet på O(n2). På grund af dette er indsættelsessortering heller ikke egnet til sortering af store lister.
Hvad er forskellen mellem boblesortering og indsættelsessortering?
Selv om både boblesorterings- og indsættelsessorteringsalgoritmerne har gennemsnitlige sagstidskompleksiteter på O(n2), bliver boblesortering næsten hele tiden bedre end indsættelsessorteringen. 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. Der er også en variant af indsættelsessortering kaldet shell-sortering, som har en tidskompleksitet på O(n3/2), hvilket ville gøre det muligt at bruge den praktisk. Desuden er indsættelsessortering meget effektiv til at sortere "næsten sorterede" lister sammenlignet med boblesorteringen.
