Bubblesort mot urval Sortera
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. Urvalssortering är också en sorteringsalgoritm, som börjar med att hitta minimielementet i listan och byta ut det med det första elementet. Denna process upprepas för resten av listan genom att byta element placeras i ordning.
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 urvalssortering?
Selection sort är också en annan sorteringsalgoritm som börjar med att hitta minimielementet i listan och byta ut det med det första elementet. Sedan hittas minimielementet från resten av listan (från det andra elementet till det sista elementet i listan) och byts ut med det andra elementet. Denna process upprepas för resten av listan genom att byta element placeras i ordning. Så i urvalssorteringen, i vilket steg som helst av algoritmen, är listan uppdelad i två delar där en del innehåller sorterade element och den andra delen innehåller osorterade element. Allt eftersom algoritmen fortsätter växer den sorterade listan från vänster till höger. Urvalssortering har också en genomsnittlig falltidskomplexitet på O(n2). Därför är den inte heller lämplig för att sortera stora listor.
Vad är skillnaden mellan bubbelsortering och urvalssortering?
Även om både bubbelsorteringsalgoritmen och urvalssorteringsalgoritmen har en genomsnittlig falltidskomplexitet av O(n2), överträffas bubbelsortering nästan hela tiden av urvalssorteringen. 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. Stabilitet är en annan skillnad i dessa två algoritmer. En stabil sorteringsalgoritm är en sorteringsalgoritm som behåller ordningen på poster om listan innehåller element med samma värde. I den meningen är urvalssortering inte en stabil algoritm medan bubbelsortering är en stabil algoritm.
