Selectie sorteren gebruiken

Selectie sorteren is een sorteertechniek die een lijstitem selecteert en vervolgens van plaats verwisselt met een ander. Het selecteert het grootste item en verwisselt het vervolgens met een item in de hoogste index van de lijst.

Het algoritme doet dit herhaaldelijk totdat de lijst is gesorteerd. Als je niet helemaal zeker weet hoe selectie sorteren werkt, ben je hier aan het juiste adres. We zullen het hieronder in meer detail uitleggen, samen met een voorbeeld.

Selectie sorteren: een nadere blik

Stel dat je de lijst hebt: [39, 82, 2, 51, 30, 42, 7]. Om de lijst te sorteren met behulp van selectiesortering, moet u eerst het hoogste nummer erin vinden.

Met de gegeven lijst is dat aantal 82. Ruil 82 met het nummer in de hoogste index (dat wil zeggen, 7).

Na de eerste doorgang is de nieuwe lijstvolgorde: [39, 7, 2, 51, 30, 42, 82]. Elke keer dat het algoritme de hele lijst doorloopt, wordt dat een "pass" genoemd.

Merk op dat de lijst een gesorteerde sublijst en een ongesorteerde sublijst bijhoudt tijdens het sorteerproces.

Verwant: Wat is Big-O-notatie?

De originele lijst begint met een gesorteerde lijst van nul items en een ongesorteerde lijst van alle items. Na de eerste doorgang heeft het een gesorteerde lijst met alleen het nummer 82.

Bij de tweede doorgang is het hoogste nummer in de ongesorteerde sublijst 51. Dit nummer wordt uitgewisseld met 42 om de nieuwe lijstvolgorde hieronder te geven:

[39, 7, 2, 42, 30, 51, 82].

Het proces wordt herhaald totdat de hele lijst is gesorteerd. Onderstaande figuur vat het hele proces samen:

De vetgedrukte zwarte cijfers geven op dat moment de hoogste lijstwaarde weer. De groene tonen de gesorteerde sublijst.

Algoritme Analyse

Om de complexiteit (met behulp van Big-O-notatie) van dit algoritme te krijgen, volgt u hieronder:

Bij de eerste doorgang worden (n-1) vergelijkingen gemaakt. Bij de tweede doorgang, (n-2). Bij de derde doorgang, (n-3) enzovoort tot de (n-1)e doorgang die slechts één vergelijking maakt.

Het samenvatten van de vergelijkingen zoals hieronder geeft:

(n-1)+ (n-1)+ (n-1)+...+1 = ((n-1)n)/2.

Daarom is selectie sortering O(n²).

Code-implementatie

De code toont functies die u kunt gebruiken voor het uitvoeren van selectiesortering met Python en Java.

Python:

def selectieSorteren (mijn lijst):
voor x binnen bereik (len (mijnlijst) - 1, 0, -1):
max_idx = 0
voor posn binnen bereik (1, x + 1):
if mylist[posn] > mylist[max_idx]:
max_idx = mogelijk
temp = mijn lijst[x]
mijnlijst[x] = mijnlijst[max_idx]
mijnlijst[max_idx] = temp

Java:

void selectionSort (int mijn_array[]){ 
voor (int x = 0; x < mijn_array.lengte - 1; x++) 
{ 
int-index = x; 
voor (int y = x + 1; y < mijn_array.lengte; y++){ 
if (mijn_array[y] < mijn_array[index]){ 
index = y; // vind laagste index 
} 
} 
int temp = mijn_array[index]; // temp is een tijdelijke opslag
mijn_array[index] = mijn_array[x]; 
mijn_array[x] = temp; 
}}

Doorgaan van Selectie Sorteren naar Samenvoegen Sorteren

Zoals de algoritmeanalyse hierboven heeft aangetoond, is het selectiesorteeralgoritme O(n²). Het heeft een exponentiële complexiteit en is daarom inefficiënt voor zeer grote datasets.

Een veel beter algoritme om te gebruiken is merge sort met een complexiteit van O(nlogn). En nu je weet hoe selectie sorteren werkt, zou de volgende op je studielijst voor sorteeralgoritmen de samenvoegsortering moeten zijn.

Over de auteur