Bubblesort mot infogning
Bubblesortering är en sorteringsalgoritm som fungerar genom att gå igenom listan för att sorteras upprepade gånger samtidigt som par av element som ligger intill jämförs. Om ett par element är i fel ordning byts de ut för att placera dem i rätt ordning. Denna övergång upprepas tills inga ytterligare byten krävs. Infogningssortering är också en sorteringsalgoritm, som fungerar genom att infoga ett element i inmatningslistan på rätt plats i en lista som redan är sorterad. Denna process tillämpas upprepade gånger tills listan är sorterad.
Vad är Bubble Sort?
Bubblesortering är en sorteringsalgoritm som fungerar genom att gå igenom listan för att sorteras upprepade gånger samtidigt som par av element som ligger intill jämförs. Om ett par element är i fel ordning byts de ut för att placera dem i rätt ordning. Denna genomgång upprepas tills inga ytterligare byten krävs (vilket innebär att listan är sorterad). Eftersom de mindre elementen i listan kommer till toppen när en bubbla kommer till ytan, får den namnet bubble sort. Bubblesortering är en mycket enkel sorteringsalgoritm men den har en genomsnittlig falltidskomplexitet på O(n2) när man sorterar en lista med n element. På grund av detta är bubbelsortering inte lämplig för att sortera listor med ett stort antal element. Men på grund av dess enkelhet lärs bubbelsortering ut under introduktioner till algoritmer.
Vad är insättningssortering?
Infogningssortering är en annan sorteringsalgoritm, som fungerar genom att infoga ett element i inmatningslistan till rätt position i en lista (som redan är sorterad). Denna process tillämpas upprepade gånger tills listan är sorterad. Vid insättningssortering utförs sortering på plats. Därför kommer de första i+1-posterna i listan att sorteras efter iterationen av algoritmen och resten av listan kommer att vara osorterad. Vid varje iteration kommer det första elementet i den osorterade delen av listan att tas och infogas på rätt plats i den sorterade delen av listan. Insättningssortering har en genomsnittlig falltidskomplexitet på O(n2). På grund av detta är insättningssorteringen inte heller lämplig för sortering av stora listor.
Vad är skillnaden mellan bubblesortering och insättningssortering?
Även om både bubbelsorterings- och infogningssorteringsalgoritmerna har en genomsnittlig falltidskomplexitet av O(n2), så överträffas bubbelsortering nästan hela tiden av infogningssorteringen. Detta beror på antalet byten som behövs av de två algoritmerna (bubbelsortering behöver fler byten). Men på grund av bubbelsorteringens enkelhet är dess kodstorlek mycket liten. Det finns också en variant av insättningssortering som kallas skalsorteringen, som har en tidskomplexitet på O(n3/2), vilket skulle göra det möjligt att använda den praktiskt. Dessutom är insättningssorteringen mycket effektiv för att sortera "nästan sorterade" listor, jämfört med bubbelsorteringen.
