Innehåll

• Jämförelsediagram
• Definition av Bubble Sort
• Definition av urvalssortering
• Slutsats

Sortering är en av de viktigaste uppgifterna i datorprogram där elementen i en matris är ordnade i någon särskild ordning. Sortering gör det lättare att söka. Bubbelsortering och urvalssortering är sorteringsalgoritmerna som kan differentieras genom de metoder som de använder för sortering. Bubbelsorter utbyter i huvudsak elementen medan urvalssortering utför sorteringen genom att välja elementet.

En annan betydande skillnad mellan de två är att bubbelsorter är en stabil algoritm medan urvalssortering är en instabil algoritm. En algoritm anses vara stabil elementen med samma nyckel som inträffade i samma ordning som de inträffade före sortering i listan eller arrayen. I allmänhet använder de flesta stabila och snabba algoritmer extra minne.

1. Jämförelsediagram
2. Definition
3. Viktiga skillnader
4. Slutsats

Jämförelsediagram

Grund för jämförelse	Bubbelsorter	Urvalssortering
Grundläggande	Intilliggande element jämförs och bytas	Största element väljs och byts med det sista elementet (i fallande stigande ordning).
Bästa falltidskomplexitet	På)	På2)
Effektivitet	Ineffektiv	Förbättrad effektivitet jämfört med bubbelsortering
Stabil	Ja	Nej
Metod	utbyte	Urval
Fart	Långsam	Snabbt jämfört med bubbelsortering

Definition av Bubble Sort

Bubbelsorter är den enklaste iterativa algoritmen fungerar genom att jämföra varje objekt eller element med objektet bredvid det och byta ut dem vid behov. I enkla ord jämförs det första och andra elementet i listan och byter den om inte de är i specifik ordning. På liknande sätt jämförs och byts andra element, 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 nummerelementen i en matris. Det största elementet skulle vara på n: e positionen efter den första iterationen. Och efter varje iteration minskar antalet jämförelser och till slut upprepas endast en jämförelse.

Denna algoritm är den långsammaste sorteringsalgoritmen. Bästa fallskomplexiteten (när listan är i ordning) av Bubble-sorten är av ordning n (På)), och i värsta fall är komplexiteten På²). I bästa fall är det av ordning n eftersom det bara jämför elementen och inte byter dem. Denna teknik kräver också ytterligare utrymme för att lagra den temporära variabeln.

Definition av urvalssortering

Urvalssortering har uppnått något bättre prestanda och är effektivare än bubbelsorteringsalgoritmen. Anta att vi vill ordna en matris i stigande ordning, då fungerar det genom att hitta det största elementet och byta ut det med det sista elementet, och upprepa följande process i undermatriserna tills hela listan är sorterad.

Vid val av sortering gör den sorterade och osorterade matrisen ingen skillnad och förbrukar en ordning av n² (På²)) i både bästa och värsta fall komplexitet. Urvalssortering är snabbare än Bubblesortering.

1. Vid bubbelsorteringen jämförs och byts varje element och dess angränsande element vid behov. Å andra sidan fungerar urvalsortering genom att välja elementet och byta det specifika elementet med det sista elementet. Det valda elementet kan vara störst eller minsta beroende på ordningen, dvs stigande eller fallande.
2. Det värsta fallet är samma i båda algoritmerna, dvs O (n²), men bästa komplexitet är annorlunda. Bubble sortering tar en ordning av n tid medan val sortering förbrukar en ordning av n² tid.
3. Bubbelsortering är en stabil algoritm, däremot är urvalssorteringen instabil.
4. Urvalssorteringsalgoritm är snabb och effektiv jämfört med bubbelsortering som är mycket långsam och ineffektiv.

Slutsats

Bubblesorteringsalgoritm anses vara den mest enkla och ineffektiva algoritmen, men urvalsorteringsalgoritmen är effektiv jämfört med bubbelsorteringen. Bubbelsorter förbrukar också extra utrymme för lagring av tillfällig variabel och behöver fler byten.