Home-theater-designers
Utvalgssortering er en sorteringsteknikk som velger et listeelement og deretter bytter plass med et annet. Den velger det største elementet og bytter det deretter med et element i listens høyeste indeks.
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 vil forklare det mer grundig nedenfor, sammen med å vise deg et eksempel.
Utvalgssortering: Et nærmere blikk
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 dette tallet 82. Bytt 82 med tallet i den høyeste indeksen (det vil si 7).
Etter det første passet 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 opprettholder en sortert underliste og en usortert deleliste under sorteringsprosessen.
windows 10 sovner ikke
I slekt: Hva er Big-O Notation?
Den originale listen begynner med en sortert liste med null elementer og en usortert liste over alle elementene. Etter den første pasningen har den en sortert liste som bare har tallet 82.
Ved den andre passeringen vil det høyeste tallet i den usorterte delelisten være 51. Dette nummeret vil bli byttet ut med 42 for å gi den nye listen rekkefølge nedenfor:
hvorfor bruker krom så mye minne?
[39, 7, 2, 42, 30, 51, 82].
Prosessen gjentas til hele listen er sortert. Figuren nedenfor oppsummerer hele prosessen:
Tallene med fet svart viser den høyeste listeverdien på den tiden. De i grønt viser den sorterte underlisten.
Algoritme analyse
For å få kompleksiteten (ved bruk av Big-O-notasjon) til denne algoritmen, følg opp nedenfor:
På det første passet gjøres (n-1) sammenligninger. På den andre pasningen, (n-2). På tredje pass, (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 utvalgssorteringen O (n2).
Kodeimplementering
Koden viser funksjoner du kan bruke til å utføre utvalgssortering ved hjelp av Python og Java.
Python:
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] = tempJava:
void selectionSort(int my_array[]){
for (int x = 0; x {
int index = x;
for (int y = x + 1; y if (my_array[y] 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å videre fra utvalg Sorter til flette Sorter
Som algoritmeanalysen ovenfor har vist, er utvalgssorteringsalgoritmen O (n2). Den har en eksponentiell kompleksitet og er derfor ineffektiv for svært store datasett.
hvordan finne noens ønskeliste på amazon
En mye bedre algoritme å bruke ville være sammenslåingssort med kompleksiteten O (nlogn). Og nå vet du hvordan utvalgssortering fungerer. Neste opp på studielisten for sorteringsalgoritmer bør være sammenslåingssorteringen.
Dele Dele kvitring E -post De 8 beste nettstedene for å laste ned lydbøker gratisLydbøker er en flott underholdningskilde, og mye lettere å fordøye. Her er de åtte beste nettstedene der du kan laste dem ned gratis.
Les neste Relaterte temaer- Programmering
- Programmering
- Algoritmer
Jerome er personalforfatter på MakeUseOf. Han dekker artikler om programmering og Linux. Han er også en kryptoentusiast og holder alltid oversikt over kryptoindustrien.
Mer fra Jerome DavidsonAbonner på vårt nyhetsbrev
Bli med i vårt nyhetsbrev for tekniske tips, anmeldelser, gratis ebøker og eksklusive tilbud!
Klikk her for å abonnere