Innehåll
Att beställa en uppsättning objekt i en lista är en vanlig uppgift vid programmering. Ofta kan en människa utföra denna uppgift intuitivt. Ett datorprogram måste dock följa en exakt sekvens av instruktioner för att slutföra det, och den sekvensen kallas en algoritm. En beställningsalgoritm är en metod som används för att placera en lista med oorganiserade artiklar i en given order. Beställningssekvensen bestäms av en nyckel. Det finns flera sorteringsalgoritmer som skiljer sig åt när det gäller effektivitet och prestanda. Några kända och viktiga av denna typ inkluderar: bubblasortering, urvalsortering, insättningssortering och snabbsortering.
Bubblesortering
Bubblasorteringen byter upprepade gånger intilliggande element som inte är i ordning förrän hela listan med artiklar är i ordning. På detta sätt flyter objekten i listan enligt deras värden, med den största (i fallet med stigande sortering) som går till slutet i slutet av varje iteration.
Den största fördelen med denna algoritm är att dess implementering är enkel och känd. Dessutom, i bubblasorteringen, ändras elementen platser utan att använda tillfällig lagring, vilket gör utrymmeskravet minimalt. Den största nackdelen är att det inte visar bra resultat när listan innehåller många objekt. Detta beror på att denna typ av sortering kräver n² bearbetningssteg för varje n antal element som ska sorteras. Därför är bubblasorten lämplig för akademisk utbildning, men inte för applikationer i verkliga livet.
Urvalssortering
Urvalssökningen söker upprepade gånger i listan med objekt, väljer ett element åt gången och placerar det i rätt position i sekvensen.
Den största fördelen med urvalssortering är att den fungerar bra på en kort lista. Eftersom det är en algoritm för platsbeställning behöver den inte tillfällig lagring utöver vad som är nödvändigt för att lagra den ursprungliga listan. Den största nackdelen är dess låga effektivitet på stora listor. Liksom bubblasorteringen kräver det antal steg för varje n-element. Dessutom påverkas dess prestanda lätt av artikelns ursprungliga ordning före sorteringsprocessen. På grund av detta är den här urvalstypen endast lämplig för en lista där få element är i slumpmässig ordning.
Insättningssortering
Insättningssorten skannar listan upprepade gånger och infogar varje gång ett objekt från den ordnade sekvensen i rätt position.
Den största fördelen med att sortera efter infogning är dess enkelhet, förutom att visa bra prestanda i små listor. Det är en platsbeställningsalgoritm, så utrymmeskravet är minimalt. Nackdelen är att den inte fungerar lika bra som andra sorteringsalgoritmer. Med n² steg som behövs för att fungera fungerar inte insättningssorten också bra med stora listor. Det är dock särskilt användbart med listor med få objekt.
Snabb sortering
Snabb sortering fungerar på principen om delning och erövring. Först delar den artikellistan i två underlistor baserat på ett pivotelement. Alla element i den första underlistan är ordnade så att de är mindre än pivoten, medan alla element i den andra sublistan är ordnade att vara större än pivoten. Samma partitionerings- och organisationsprocess utförs upprepade gånger på de resulterande underlistorna tills hela listan är organiserad.
Snabb sortering anses av vissa vara den bästa sorteringsalgoritmen på grund av dess betydande effektivitetsfördel, eftersom den fungerar bra med en stor lista med artiklar. Genom att beställa på plats finns det inget behov av ytterligare lagringsutrymme. Den lilla nackdelen som den uppvisar är att dess sämsta prestanda liknar den genomsnittliga prestandan för de andra algoritmer som beskrivs ovan. Det är dock viktigt att notera att detta värsta fall är mycket sällsynt. Mer generellt ger snabb sortering den mest effektiva och mest använda metoden för att organisera en lista av alla storlekar.
