En annan stor skillnad mellan de två är att bubbla sorterar är stabil algoritm medan urvalstyp är en instabil algoritm. En algoritm anses vara stabil, elementen med samma nyckel förekommer i samma ordning som de förekom sortering i listan eller arrayen. I allmänhet använder de flesta stabila och snabba algoritmer extra minne.
Jämförelsediagram
| Grunder för jämförelse | Bubbla sortera | Urval sortera |
|---|---|---|
| Grundläggande | Intilliggande element jämförs och bytas | Största elementet väljs och byts ut med det sista elementet (vid stigande ordning). |
| Bästa fallstidskomplexitet | På) | O (n2) |
| Effektivitet | Ineffektiv | Förbättrad effektivitet jämfört med bubbelsort |
| Stabil | Ja | Nej |
| Metod | utbyte | Urval |
| Fart | Långsam | Snabbt jämfört med bubbla sortera |
Definition av bubbelsort
Bubbelsort är den enklaste iterativa algoritmen genom att jämföra varje objekt eller element med objektet bredvid det och byta dem om det behövs. I enkla ord jämförs det första och andra elementet i listan och byter det om de inte är specifika. På liknande sätt jämförs och byts det andra och det tredje elementet, och denna jämförelse och byte fortsätter till slutet av listan. Antalet jämförelser i den första iterationen är n-1 där n är talelementen i en array. Det största elementet skulle vara i nth position efter den första iterationen. Och efter varje iteration minskar antalet jämförelser och slutligen iteration sker endast en jämförelse.
Denna algoritm är den långsammaste sorteringsalgoritmen. Den bästa fallskomplexiteten (när listan är i ordning) av typen Bubble är av order n ( O (n) ), och värst är komplexiteten O (n2) . I bästa fall är det av order n eftersom det bara jämför elementen och byter inte dem. Denna teknik kräver också extra utrymme för att lagra den temporära variabeln.
Definition av urvalssortering
Urvalssortering har uppnått något bättre prestanda och är effektiv än bubbelsortalgoritmen. Antag att vi vill ordna en array i stigande ordning då fungerar den genom att hitta det största elementet och utbyta det med det sista elementet och upprepa följande process på delraderna tills hela listan är sorterad.
Viktiga skillnader mellan bubbelsortering och urvalssortering
- I sorten bubbla jämförs och byts varje element och dess närliggande element om det behövs. Å andra sidan fungerar sorterings sorter genom att välja elementet och byta det aktuella elementet med det sista elementet. Det valda elementet kan vara störst eller minsta beroende på beställningen, dvs stigande eller nedåtgående.
- Värsta komplexiteten är densamma i både algoritmerna, dvs O (n2), men den bästa komplexiteten är annorlunda. Bubbelsort tar en order av n-tiden medan urvalskortet förbrukar en order av n2-tid.
- Bubbelsort är en stabil algoritm, däremot är sortimentet instabilt.
- Urvalssorteringsalgoritmen är snabb och effektiv jämfört med bubbelsort som är mycket långsam och ineffektiv.
Slutsats
Bubbelsorteringsalgoritmen anses vara den enklaste och ineffektiva algoritmen, men sorteringsalgoritmen är effektiv jämfört med bubbelsort. Bubbelsortet förbrukar också extra utrymme för lagring av temporär variabel och behöver fler swappar.
