Hur man använder urvalsortering

Markeringssortering är en sorteringsteknik som väljer ett listobjekt och sedan byter plats med ett annat. Det väljer det största objektet och byter det sedan med ett objekt i listans högsta index.

Algoritmen gör detta upprepade gånger tills listan sorteras. Om du inte är helt säker på hur valssortering fungerar, har du kommit till rätt ställe. Vi förklarar det mer ingående nedan och visar ett exempel.

Urvalssortering: En närmare titt

Antag att du har listan: [39, 82, 2, 51, 30, 42, 7]. För att sortera listan med hjälp av urvalsortering måste du först hitta det högsta numret i den.

Med den angivna listan är antalet 82. Byt 82 med siffran i det högsta indexet (det vill säga 7).

Efter det första passet blir den nya listordningen: [39, 7, 2, 51, 30, 42, 82]. Varje gång algoritmen går igenom hela listan kallas det ett "pass".

Observera att listan har en sorterad underlista och en osorterad underlista under sorteringsprocessen.

Relaterad: Vad är Big-O-notering?

Originallistan börjar med en sorterad lista med noll objekt och en osorterad lista över alla artiklar. Sedan efter det första passet har den en sorterad lista med endast siffran 82.

Vid det andra passet kommer det högsta antalet i den osorterade underlistan att vara 51. Detta nummer kommer att utbytas med 42 för att ge den nya listan ordning nedan:

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

Processen upprepas tills hela listan är sorterad. Figuren nedan sammanfattar hela processen:

Siffrorna i fet svart visar det högsta listvärdet vid den tiden. De i grönt visar den sorterade underlistan.

Algoritmeanalys

För att få komplexiteten (med Big-O-notering) för denna algoritm, följ nedan:

Vid det första passet görs (n-1) jämförelser. Vid det andra passet, (n-2). Vid det tredje passet, (n-3) och så vidare tills det (n-1) passet som bara gör en jämförelse.

Sammanfattningen av jämförelserna enligt nedan ger:

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

Därför är valssorteringen O (n²).

Kodimplementering

Koden visar funktioner som du kan använda för att utföra urvalsortering med Python och Java.

Pytonorm:

def selectionSort (min lista):
för x i intervallet (len (min lista) - 1, 0, -1):
max_idx = 0
för posn inom räckvidd (1, x + 1):
om min lista [posn]> min lista [max_idx]:
max_idx = posn
temp = min lista [x]
minlista [x] = minlista [max_idx]
minlista [max_idx] = temp

Java:

ogiltigt urvalSort (int my_array []) { 
för (int x = 0; x { 
int index = x; 
för (int y = x + 1; y om (min_array [y] index = y; // hitta lägsta index 
} 
} 
int temp = min_array [index]; // temp är en tillfällig lagring
min_array [index] = min_array [x]; 
min_array [x] = temp; 
}}

Gå vidare från urval Sortera till Slå samman Sortera

Som algoritmanalysen ovan har visat är valssorteringsalgoritmen O (n²). Den har en exponentiell komplexitet och är därför ineffektiv för mycket stora datamängder.

En mycket bättre algoritm att använda skulle vara sammanslagningssortering med komplexiteten O (nlogn). Och nu vet du hur urvalssortering fungerar, nästa i din studielista för sorteringsalgoritmer ska vara sammanslagningssorteringen.

Om författaren