Skillnad mellan bubbelsortering och urvalssortering

Bubbla Sort vs Urval Sortera

Bubbelsort är en sorteringsalgoritm som fungerar genom att gå igenom listan som ska sorteras upprepade gånger medan man jämför parpar av element som ligger intill. Om ett par element är i fel ordning bytas de för att placera dem i rätt ordning. Denna traverse upprepas tills inga ytterligare swappar krävs. Sorteringsval är också en sorteringsalgoritm, som börjar med att hitta det minsta elementet i listan och byta det med det första elementet. Denna process upprepas för resten av listan genom att placera bytte element i ordning.

Vad är bubbelsort?

Bubbelsort är en sorteringsalgoritm som fungerar genom att gå igenom listan som ska sorteras upprepade gånger medan man jämför parpar av element som ligger intill. Om ett par element är i fel ordning bytas de för att placera dem i rätt ordning. Denna traverse upprepas tills inga ytterligare swappar krävs (vilket innebär att listan sorteras). Eftersom de mindre elementen i listan kommer till toppen när en bubbla kommer till ytan, ges den namnet bubbelsort. Bubbelsort är en mycket enkel sorteringsalgoritm men den har en genomsnittlig fallkomplexitet på O (n2) när du sorterar en lista med n-element. På grund av detta är bubbelsort inte lämpligt för sortering av listor med ett stort antal element. Men på grund av sin enkelhet lärs bubbelsort under introduktioner till algoritmer.

Vad är Selection Sort?

Urvalssortering är också en annan sorteringsalgoritm som börjar med att hitta det minsta elementet i listan och byta det med det första elementet. Därefter finns minimumselementet från resten av listan (från det andra elementet till det sista elementet i listan) och bytts med det andra elementet. Denna process upprepas för resten av listan genom att placera bytte element i ordning. Så i valet sorteras, vid något steg i algoritmen, är listan uppdelad i två delar där en del innehåller sorterade element och den andra delen innehåller osorterade element. När algoritmen fortsätter växer den sorterade listan från vänster till höger. Urvalsklassen har också en genomsnittlig fallkomplexitet på O (n2). Därför är det inte heller lämpligt att sortera stora listor.

Vad är skillnaden mellan bubbelsortering och urvalssortering?

Även om både sorteringsalgoritmerna för bubbla sorterar och urval har genomsnittliga fallkomplexiteter av O (n2) är bubbelsorten nästan alltid överträffad av urvalssorten. Detta beror på antalet swappar som behövs av de två algoritmerna (bubbelsorter behöver fler swappar). Men på grund av enkelhetens bubbelsort är kodens storlek mycket liten. Stabilitet är en annan skillnad i dessa två algoritmer. En stabil sorteringsalgoritm är en sorteringsalgoritm som behåller ordning av poster om listan innehåller element med lika värde. I den meningen är urvalssort inte en stabil algoritm medan bubbelsort är en stabil algoritm.