Urvalssortering är en sorteringsteknik som väljer ett listobjekt och sedan byter plats med ett annat. Den väljer det största objektet och byter sedan ut det med ett objekt i listans högsta index.
Algoritmen gör detta upprepade gånger tills listan är sorterad. Om du inte är helt säker på hur urvalssorteringen fungerar, har du kommit till rätt ställe. Vi kommer att förklara det mer djupgående nedan, tillsammans med att visa dig ett exempel.
Urvalssortering: En närmare titt
Anta att du har listan: [39, 82, 2, 51, 30, 42, 7]. För att sortera listan med hjälp av urvalssortering måste du först hitta det högsta numret i den.
Med den givna listan är det numret 82. Byt 82 med numret i det högsta indexet (det vill säga 7).
Efter det första passet kommer den nya listordningen att vara: [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.
Den ursprungliga listan börjar med en sorterad lista med noll artiklar och en osorterad lista över alla objekt. Sedan efter det första passet har den en sorterad lista med bara numret 82.
Vid det andra passet kommer det högsta numret i den osorterade underlistan att vara 51. Detta nummer kommer att bytas ut mot 42 för att ge den nya listordningen nedan:
[39, 7, 2, 42, 30, 51, 82].
Processen upprepas tills hela listan är sorterad. Bilden 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.
Algoritmanalys
För att få komplexiteten (med hjälp av Big-O-notation) för denna algoritm, följ nedan:
Vid första passet görs (n-1) jämförelser. På det andra passet, (n-2). På det tredje passet, (n-3) och så vidare tills det (n-1):e passet som bara gör en jämförelse.
Att sammanfatta jämförelserna enligt nedan ger:
(n-1)+ (n-1)+ (n-1)+…+1 = ((n-1)n)/2.
Därför är urvalssorteringen O(n2).
Kodimplementering
Koden visar funktioner du kan använda för att utföra urvalssortering med Python och Java.
Pytonorm:
def selectionSort(mylist):
for x in range(len(mylist) - 1, 0, -1):
max_idx = 0
for posn in range(1, x + 1):
if mylist[posn] > mylist[max_idx]:
max_idx = posn
temp = mylist[x]
mylist[x] = mylist[max_idx]
mylist[max_idx] = temp
Java:
void selectionSort(int my_array[]){
for (int x = 0; x < my_array.length - 1; x++)
{
int index = x;
for (int y = x + 1; y < my_array.length; y++){
if (my_array[y] < my_array[index]){
index = y; // find lowest index
}
}
int temp = my_array[index]; // temp is a temporary storage
my_array[index] = my_array[x];
my_array[x] = temp;
}}
Går vidare från urvalssortering till sammanslagningssortering
Som algoritmanalysen ovan har visat är urvalssorteringsalgoritmen O(n2). 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 merge sort med komplexiteten O(nlogn). Och nu vet du hur urvalssorteringen fungerar, nästa på din studielista för sorteringsalgoritmer bör vara sammanslagningssorteringen.
Om författaren
Jerome Davidson (33 artiklar publicerade)
Jerome är personalskribent på MakeUseOf. Han täcker artiklar om programmering och Linux. Han är också en kryptoentusiast och håller alltid koll på kryptoindustrin.
Mer från Jerome Davidson
Prenumerera på vårt nyhetsbrev
Gå med i vårt nyhetsbrev för tekniska tips, recensioner, free e-böcker och exklusiva erbjudanden!
Klicka här för att prenumerera
