Sådan bruges valgsortering

Selektionssortering er en sorteringsteknik, der vælger et listeelement og derefter bytter plads med en anden. Det vælger det største element og bytter det derefter med et element i det højeste indeks på listen.

Algoritmen gør dette gentagne gange, indtil listen er sorteret. Hvis du ikke er helt sikker på, hvordan valg af sortering fungerer, er du kommet til det rigtige sted. Vi forklarer det nærmere nedenfor og viser dig et eksempel.

Valg af sortering: Et nærmere blik

Antag at du har listen: [39, 82, 2, 51, 30, 42, 7]. For at sortere listen ved hjælp af valgsortering, skal du først finde det højeste tal i den.

Med den givne liste er tallet 82. Byt 82 med tallet i det højeste indeks (dvs. 7).

Efter det første pass, vil den nye listeordre være: [39, 7, 2, 51, 30, 42, 82]. Hver gang algoritmen gennemgår hele listen, kaldes det et "pas".

Bemærk, at listen opretholder en sorteret underliste og en usorteret underliste under sorteringsprocessen.

Relaterede: Hvad er Big-O Notation?

Den originale liste begynder med en sorteret liste med nul varer og en usorteret liste over alle elementerne. Derefter efter den første pasning har den en sorteret liste med kun nummeret 82.

Ved det andet pass er det højeste tal i den usorterede underliste 51. Dette nummer udveksles med 42 for at give den nye listeordre nedenfor:

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

Processen gentages, indtil hele listen er sorteret. Figuren nedenfor opsummerer hele processen:

Tallene i fed sort viser den højeste listeværdi på det tidspunkt. De grønne viser den sorterede underliste.

Algoritmeanalyse

For at få kompleksiteten (ved hjælp af Big-O notation) af denne algoritme skal du følge nedenstående:

Ved første gennemgang foretages (n-1) sammenligninger. På det andet pass, (n-2). På det tredje pass, (n-3) og så videre indtil (n-1) th pass, som kun foretager en sammenligning.

Sammenfatning af sammenligningerne som nedenfor giver:

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

Derfor er valgsortering O (n²).

Kodeimplementering

Koden viser funktioner, du kan bruge til at udføre valgsortering ved hjælp af Python og Java.

Python:

def selectionSort (min liste):
for x inden for rækkevidde (len (min liste) - 1, 0, -1):
max_idx = 0
for posn inden for rækkevidde (1, x + 1):
hvis min liste [posn]> min liste [max_idx]:
max_idx = posn
temp = min liste [x]
mylist [x] = mylist [max_idx]
mylist [max_idx] = temp

Java:

tomrumsvalgSort (int my_array []) { 
for (int x = 0; x { 
int-indeks = x; 
for (int y = x + 1; y hvis (min_array [y] indeks = y; // find laveste indeks 
} 
} 
int temp = min_array [indeks]; // temp er en midlertidig lagring
min_array [index] = min_array [x]; 
min_array [x] = temp; 
}}

Gå videre fra markering Sort til Merge Sort

Som algoritmeanalysen ovenfor har vist, er valgsorteringsalgoritmen O (n²). Det har en eksponentiel kompleksitet og er derfor ineffektiv for meget store datasæt.

En meget bedre algoritme at bruge ville være flettsortering med en kompleksitet af O (nlogn). Og nu ved du, hvordan udvælgelsessortering fungerer, næste på din undersøgelsesliste til sorteringsalgoritmer skal være fusioneringssorteringen.

Om forfatteren