Udvælgelsessortering: Algoritme forklaret med Python Kodeeksempel

Hvad er udvalgssortering?

UDVALG SORT er en sammenligningssorteringsalgoritme, der bruges til at sortere en tilfældig liste over elementer i stigende rækkefølge. Sammenligningen kræver ikke meget ekstra plads. Det kræver kun én ekstra hukommelsesplads til den tidsmæssige variabel.

Dette er kendt som på plads sortering. Udvælgelsessorten har en tidskompleksitet på O(n²) hvor n er det samlede antal elementer på listen. Tidskompleksiteten måler antallet af iterationer, der kræves for at sortere listen. Listen er opdelt i to partitioner: Den første liste indeholder sorterede elementer, mens den anden liste indeholder usorterede elementer.

Som standard er den sorterede liste tom, og den usorterede liste indeholder alle elementerne. Den usorterede liste scannes derefter for minimumsværdien, som derefter placeres i den sorterede liste. Denne proces gentages, indtil alle værdier er blevet sammenlignet og sorteret.

Hvordan fungerer udvælgelsessortering?

Det første element i den usorterede partition sammenlignes med alle værdierne til højre for at kontrollere, om det er minimumsværdien. Hvis det ikke er minimumsværdien, byttes dens position med minimumsværdien.

Eksempel

For eksempel, hvis indekset for minimumsværdien er 3, placeres værdien af elementet med indeks 3 ved indeks 0, mens værdien, der var ved indeks 0, placeres ved indeks 3. Hvis det første element i den usorterede partition er minimumsværdien, så returnerer den sine positioner.
Elementet, der er blevet bestemt som minimumsværdi, flyttes derefter til partitionen i venstre side, som er den sorterede liste.
Den opdelte side har nu ét element, mens den uopdelte side har (n – 1) elementer, hvor n er det samlede antal elementer på listen. Denne proces gentages igen og igen, indtil alle elementer er blevet sammenlignet og sorteret ud fra deres værdier.

Problem Definition

En liste over elementer, der er i tilfældig rækkefølge, skal sorteres i stigende rækkefølge. Overvej følgende liste som et eksempel.

[21,6,9,33,3]

Ovenstående liste skal sorteres for at give følgende resultater

[3,6,9,21,33]

Løsning (algoritme)

Trin 1) Få værdien af n, som er den samlede størrelse af arrayet

Trin 2) Opdel listen i sorterede og usorterede sektioner. Den sorterede sektion er til at begynde med tom, mens den usorterede sektion indeholder hele listen

Trin 3) Vælg minimumsværdien fra den upartitionerede sektion og placer den i den sorterede sektion.

Trin 4) Gentag processen (n – 1) gange, indtil alle elementerne på listen er blevet sorteret.

Visuel repræsentation

Med en liste med fem elementer illustrerer de følgende billeder, hvordan udvælgelsessorteringsalgoritmen itererer gennem værdierne, når de sorteres.

Følgende billede viser den usorterede liste

Trin 1)

Den første værdi 21 sammenlignes med resten af værdierne for at kontrollere, om det er minimumsværdien.

3 er minimumsværdien, så positionerne 21 og 3 er byttet om. Værdierne med grøn baggrund repræsenterer listens sorterede partition.

Trin 2)

Værdien 6, som er det første element i den usorterede partition, sammenlignes med resten af værdierne for at finde ud af, om der findes en lavere værdi

Værdien 6 er minimumsværdien, så den bevarer sin position.

Trin 3)

Det første element i den usorterede liste med værdien 9 sammenlignes med resten af værdierne for at kontrollere, om det er minimumsværdien.

Værdien 9 er minimumsværdien, så den bevarer sin position i den sorterede partition.

Trin 4)

Værdien 33 sammenlignes med resten af værdierne.

Værdien 21 er lavere end 33, så positionerne er byttet om for at producere ovenstående nye liste.

Trin 5)

Vi har kun én værdi tilbage i den uopdelte liste. Derfor er det allerede sorteret.

Den endelige liste er som den, der er vist på billedet ovenfor.

Valg Sorter Program vha Python 3

Den følgende kode viser udvælgelsessorteringsimplementeringen vha Python 3

def selectionSort( itemsList ):
    n = len( itemsList )
    for i in range( n - 1 ): 
        minValueIndex = i

        for j in range( i + 1, n ):
            if itemsList[j] < itemsList[minValueIndex] :
                minValueIndex = j

        if minValueIndex != i :
            temp = itemsList[i]
            itemsList[i] = itemsList[minValueIndex]
            itemsList[minValueIndex] = temp

    return itemsList


el = [21,6,9,33,3]

print(selectionSort(el))

Kør ovenstående kode giver følgende resultater

[3, 6, 9, 21, 33]

Kode Forklaring

Forklaringen på koden er som følger

Her er kodeforklaring:

Definerer en funktion ved navn selectSort
Henter det samlede antal elementer på listen. Vi har brug for dette for at bestemme antallet af gennemløb, der skal foretages, når vi sammenligner værdier.
Ydre sløjfe. Bruger løkken til at gentage listens værdier. Antallet af iterationer er (n – 1). Værdien af n er 5, så (5 – 1) giver os 4. Det betyder, at de ydre iterationer udføres 4 gange. I hver iteration tildeles værdien af variablen i til variablen minValueIndex
Indre sløjfe. Bruger løkken til at sammenligne værdien længst til venstre med de andre værdier på højre side. Værdien for j starter dog ikke ved indeks 0. Den starter ved (i + 1). Dette udelukker de værdier, der allerede er sorteret, så vi fokuserer på varer, der endnu ikke er sorteret.
Finder minimumsværdien i den usorterede liste og placerer den i dens korrekte position
Opdaterer værdien af minValueIndex, når byttebetingelsen er sand
Sammenligner værdierne af indekstal minValueIndex og i for at se, om de ikke er ens
Værdien længst til venstre er gemt i en tidsvariabel
Den nederste værdi fra højre side indtager den første position
Værdien, der blev gemt i den tidsmæssige værdi, gemmes i den position, der tidligere blev holdt af minimumsværdien
Returnerer den sorterede liste som funktionsresultat
Opretter en liste el, der har tilfældige tal
Udskriv den sorterede liste efter at have kaldt udvælgelsen Sorteringsfunktion med indtastning af el som parameter.

Tidskompleksitet af udvalgssortering

Sorteringskompleksiteten bruges til at udtrykke antallet af eksekveringstider, det tager at sortere listen. Implementeringen har to sløjfer.

Den ydre sløjfe, som vælger værdierne én efter én fra listen, udføres n gange, hvor n er det samlede antal værdier på listen.

Den indre løkke, som sammenligner værdien fra den ydre løkke med resten af værdierne, udføres også n gange, hvor n er det samlede antal elementer i listen.

Derfor er antallet af henrettelser (n * n), hvilket også kan udtrykkes som O(n²).

Udvælgelsessorten har tre kategorier af kompleksitet, nemlig;

Værste tilfælde – det er her den angivne liste er i faldende rækkefølge. Algoritmen udfører det maksimale antal eksekveringer, som er udtrykt som [Big-O] O(n)²)
Bedste sag – dette sker, når den angivne liste allerede er sorteret. Algoritmen udfører det mindste antal henrettelser, som er udtrykt som [Big-Omega] ?(n²)
Gennemsnitligt tilfælde – dette sker, når listen er i tilfældig rækkefølge. Den gennemsnitlige kompleksitet er udtrykt som [Big-theta] ?(n²)

Udvælgelsessorten har en rumkompleksitet på O(1), da den kræver én tidsvariabel, der bruges til at bytte værdier.

Hvornår skal man bruge udvælgelsessortering?

Valgsorteringen bruges bedst, når du vil:

Du skal sortere en lille liste over elementer i stigende rækkefølge
Når omkostningerne ved at bytte værdier er ubetydelige
Den bruges også, når du skal sikre dig, at alle værdierne i listen er blevet tjekket.

Fordele ved Selection Sort

Følgende er fordelene ved udvælgelsessorten

Den klarer sig meget godt på små lister
Det er en in-place algoritme. Det kræver ikke meget plads til sortering. Der kræves kun et ekstra mellemrum for at holde den tidsmæssige variabel.
Det fungerer godt på varer, der allerede er blevet sorteret.

Ulemper ved Selection Sort

Følgende er ulemperne ved udvælgelsessorten.

Det klarer sig dårligt, når man arbejder på store lister.
Antallet af iterationer foretaget under sorteringen er n-kvadrat, hvor n er det samlede antal elementer på listen.
Andre algoritmer, såsom quicksort, har bedre ydeevne sammenlignet med udvælgelsessortering.

Resumé

Udvælgelsessortering er en in-place sammenligningsalgoritme, der bruges til at sortere en tilfældig liste i en ordnet liste. Den har en tidskompleksitet på O(n²)
Listen er opdelt i to sektioner, sorteret og usorteret. Minimumsværdien plukkes fra den usorterede sektion og placeres i den sorterede sektion.
Denne ting gentages, indtil alle elementer er blevet sorteret.
Implementering af pseudokoden i Python 3 involverer at bruge to for loops og if-sætninger for at kontrollere, om bytte er nødvendigt
Tidskompleksiteten måler antallet af trin, der kræves for at sortere listen.
Den værste tidskompleksitet opstår, når listen er i faldende rækkefølge. Den har en tidskompleksitet på [Big-O] O(n²)
Den bedste tidskompleksitet opstår, når listen allerede er i stigende rækkefølge. Det har en tidskompleksitet på [Big-Omega] ?(n²)
Den gennemsnitlige tidskompleksitet opstår, når listen er i tilfældig rækkefølge. Det har en tidskompleksitet på [Big-theta] ?(n²)
Udvælgelsessortering bruges bedst, når du har en lille liste over elementer, der skal sorteres, omkostningerne ved at bytte værdier er ligegyldige, og kontrol af alle værdierne er obligatorisk.
Udvælgelsessorten klarer sig ikke godt på store lister
Andre sorteringsalgoritmer, såsom quicksort, har bedre ydeevne sammenlignet med udvælgelsessortering.

Du kan lide: