Hvordan bruke utvalgssortering

Seleksjon er en sorteringsteknikk som velger et listeelement og deretter bytter plass med et annet. Den velger det største elementet og bytter det med et element i den høyeste indeksen på listen.

Algoritmen gjør dette gjentatte ganger til listen er sortert. Hvis du ikke er helt sikker på hvordan utvalgssortering fungerer, har du kommet til rett sted. Vi forklarer det nærmere nedenfor og viser deg et eksempel.

Valgsortering: Et nærmere utseende

Anta at du har listen: [39, 82, 2, 51, 30, 42, 7]. For å sortere listen ved hjelp av utvalgssortering, må du først finne det høyeste tallet i den.

Med den gitte listen er tallet 82. Bytt 82 med tallet i høyeste indeks (det vil si 7).

Etter første passering vil den nye listeordren være: [39, 7, 2, 51, 30, 42, 82]. Hver gang algoritmen går gjennom hele listen, kalles det et "pass".

Legg merke til at listen har en sortert underliste og en usortert underliste under sorteringsprosessen.

I slekt: Hva er Big-O Notation?

Den opprinnelige listen begynner med en sortert liste med null elementer og en usortert liste over alle elementene. Etter den første passeringen har den en sortert liste som bare har tallet 82.

Ved det andre passet vil det høyeste tallet i den usorterte underlisten være 51. Dette nummeret byttes ut med 42 for å gi den nye listeordren nedenfor:

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

Prosessen gjentas til hele listen er sortert. Figuren nedenfor oppsummerer hele prosessen:

Tallene i fet svart viser den høyeste listeverdien på den tiden. De i grønt viser den sorterte underlisten.

Algoritmeanalyse

For å få kompleksiteten (ved hjelp av Big-O-notasjon) av denne algoritmen, følger du gjennom nedenfor:

Ved første passering blir (n-1) sammenligninger gjort. På det andre passet, (n-2). På det tredje passet, (n-3) og så videre til (n-1) th pass som bare gjør en sammenligning.

Oppsummering av sammenligningene som nedenfor gir:

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

Derfor er valgsort O (n²).

Kodeimplementering

Koden viser funksjoner du kan bruke til å utføre utvalgssortering ved hjelp av Python og Java.

Python:

def selectionSort (min liste):
for x innen rekkevidde (len (min liste) - 1, 0, -1):
max_idx = 0
for posn innen rekkevidde (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:

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

Gå videre fra utvalg Sorter til Slå sammen Sorter

Som algoritmeanalysen ovenfor har vist, er valgsorteringsalgoritmen O (n²). Den har en eksponentiell kompleksitet og er derfor ineffektiv for veldig store datasett.

En mye bedre algoritme å bruke ville være flettesortering med en kompleksitet av O (nlogn). Og nå vet du hvordan utvalgssortering fungerer, neste opp på studielisten din for sorteringsalgoritmer skal være flettesorteringen.

Om forfatteren