Hvad er valgsortering?
SELECTION SORT er en sammenligningssorteringsalgoritme, der bruges til at sortere en tilfældig liste over varer i stigende rækkefølge. Sammenligningen kræver ikke meget ekstra plads. Det kræver kun en ekstra hukommelsesplads til den tidsmæssige variabel.
Dette kaldes sortering på stedet . Valgssorteringen har en tidskompleksitet på O (n 2 ), hvor n er det samlede antal varer 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 emner, mens den anden liste indeholder usorterede emner.
Den sorterede liste er som standard tom, og den usorterede liste indeholder alle elementerne. Den usorterede liste scannes derefter efter minimumsværdien, som derefter placeres på den sorterede liste. Denne proces gentages, indtil alle værdier er blevet sammenlignet og sorteret.
I denne algoritmevejledning lærer du:
- Hvad er valgsortering?
- Hvordan fungerer sortering af valg?
- Problemdefinition
- Løsning (algoritme)
- Visuel repræsentation
- Selection Sort Program ved hjælp af Python 3
- Kode Forklaring
- Tidskompleksitet af valgsortering
- Hvornår skal man bruge sortering af valg?
- Fordele ved valg af sortering
- Ulemper ved valg af sortering
Hvordan fungerer sortering af valg?
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 dets 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 i indeks 3. Hvis det første element i den usorterede partition er minimumsværdien, så returnerer den sine positioner.
- Det element, der er bestemt som minimumsværdien, flyttes derefter til partitionen på venstre side, som er den sorterede liste.
- Den partitionerede side har nu et element, mens den ikke-partitionerede side har (n - 1) elementer, hvor n er det samlede antal elementer på listen. Denne proces gentages igen og igen, indtil alle varer er blevet sammenlignet og sorteret ud fra deres værdier.
Problemdefinition
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 oprindeligt tom, mens den usorterede sektion indeholder hele listen
Trin 3) Vælg minimumsværdien fra den ikke-partitionerede sektion og placer den i den sorterede sektion.
Trin 4) Gentag processen (n - 1) gange, indtil alle elementerne på listen er sorteret.
Visuel repræsentation
På baggrund af en liste med fem elementer illustrerer de følgende billeder, hvordan algoritmen til valg af sortering gentages gennem værdierne, når de sorteres.
Det 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 den er minimumsværdien.
3 er minimumsværdien, så positionerne 21 og 3 byttes. Værdierne med en grøn baggrund repræsenterer den sorterede partition på listen.
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 opretholder 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 opretholder 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 byttes for at producere ovenstående nye liste.
Trin 5)
Vi har kun én værdi tilbage på den ikke-partitionerede liste. Derfor er den allerede sorteret.
Den endelige liste er som den, der er vist i ovenstående billede.
Selection Sort Program ved hjælp af Python 3
Den følgende kode viser implementeringen af sorteringssorteringen ved hjælp af Python 3
def selectionSort( itemsList ):n = len( itemsList )for i in range( n - 1 ):minValueIndex = ifor j in range( i + 1, n ):if itemsList[j] < itemsList[minValueIndex] :minValueIndex = jif minValueIndex != i :temp = itemsList[i]itemsList[i] = itemsList[minValueIndex]itemsList[minValueIndex] = tempreturn itemsListel = [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 kode forklaring:
- Definerer en funktion ved navn selectionSort
- Henter det samlede antal elementer på listen. Vi har brug for dette for at bestemme antallet af passeringer, der skal foretages, når vi sammenligner værdier.
- Ydre sløjfe. Bruger sløjfen til at gentage gennem værdierne på listen. Antallet af iterationer er (n - 1). Værdien af n er 5, så (5 - 1) giver os 4. Dette betyder, at de ydre iterationer udføres 4 gange. I hver iteration tildeles værdien af variablen i variablen minValueIndex
- Indre sløjfe. Bruger loop til at sammenligne den længste værdi 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 ekskluderer de værdier, der allerede er sorteret, så vi fokuserer på emner, der endnu ikke er sorteret.
- Finder minimumsværdien på den usorterede liste og placerer den i sin rette position
- Opdaterer værdien af minValueIndex, når ombytningsbetingelsen er sand
- Sammenligner værdierne for indeksnumrene minValueIndex og i for at se, om de ikke er ens
- Værdien længst til venstre er gemt i en tidsmæssig variabel
- Den lavere værdi fra højre side indtager positionen som første position
- Den værdi, 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 listeel, der har tilfældige tal
- Udskriv den sorterede liste efter at have kaldt udvalget Sorteringsfunktion, der passerer el som parameter.
Tidskompleksitet af valgsortering
Sorteringskompleksiteten bruges til at udtrykke antallet af udførelsestider, det tager at sortere listen. Implementeringen har to sløjfer.
Den ydre sløjfe, der vælger værdierne en efter en fra listen, udføres n gange, hvor n er det samlede antal værdier på listen.
Den indre sløjfe, der sammenligner værdien fra den ydre sløjfe med resten af værdierne, udføres også n gange, hvor n er det samlede antal elementer på listen.
Derfor er antallet af henrettelser (n * n), som også kan udtrykkes som O (n 2 ).
Valgsorteringen har tre kategorier af kompleksitet, nemlig;
- Værste tilfælde - det er her listen er i faldende rækkefølge. Algoritmen udfører det maksimale antal udførelser, der udtrykkes som [Big-O] O (n 2 )
- Bedste tilfælde - dette sker, når den angivne liste allerede er sorteret. Algoritmen udfører det mindste antal eksekveringer, der udtrykkes som [Big-Omega] Ω (n 2 )
- Gennemsnitlig sag - dette sker, når listen er i tilfældig rækkefølge. Den gennemsnitlige kompleksitet udtrykkes som [Big-theta] ⊝ (n 2 )
Valgssorteringen har en pladskompleksitet på O (1), da den kræver en tidsmæssig variabel, der bruges til at bytte værdier.
Hvornår skal man bruge sortering af valg?
Valgssorteringen bruges bedst, når du vil:
- Du skal sortere en lille liste over varer i stigende rækkefølge
- Når omkostningerne ved at bytte værdier er ubetydelige
- Det bruges også, når du skal sikre dig, at alle værdierne på listen er kontrolleret.
Fordele ved valg af sortering
Følgende er fordelene ved valgsorteringen
- Det fungerer meget godt på små lister
- Det er en lokal algoritme. Det kræver ikke meget plads til sortering. Der kræves kun en ekstra plads til at holde den tidsmæssige variabel.
- Det fungerer godt på emner, der allerede er sorteret.
Ulemper ved valg af sortering
Følgende er ulemperne ved valgsorteringen.
- Det fungerer dårligt, når du arbejder på store lister.
- Antallet af iterationer, der foretages under sorteringen, er n-kvadrat, hvor n er det samlede antal elementer på listen.
- Andre algoritmer, såsom quicksort, har bedre ydeevne sammenlignet med valgsorteringen.
Resumé:
- Selection sort er en stedlig sammenligningsalgoritme, der bruges til at sortere en tilfældig liste i en ordnet liste. Det har en tidskompleksitet på O (n 2 )
- Listen er opdelt i to sektioner, sorteret og usorteret. Minimumsværdien vælges fra den usorterede sektion og placeres i den sorterede sektion.
- Denne ting gentages, indtil alle varer er blevet sorteret.
- Implementering af pseudokoden i Python 3 indebærer at bruge to til sløjfer og hvis udsagn for at kontrollere, om bytte er nødvendig
- Tidskompleksiteten måler antallet af trin, der kræves for at sortere listen.
- Den værst tænkelige tidskompleksitet sker, når listen er i faldende rækkefølge. Det har en tidskompleksitet på [Big-O] O (n 2 )
- Kompleksiteten i bedste fald sker, når listen allerede er i stigende rækkefølge. Det har en tidskompleksitet på [Big-Omega] Ω (n 2 )
- Den gennemsnitlige sags tidskompleksitet sker, når listen er i tilfældig rækkefølge. Det har en tidskompleksitet på [Big-theta] ⊝ (n 2 )
- Valgssorteringen bruges bedst, når du har en lille liste over emner, der skal sorteres, omkostningerne ved at bytte værdier betyder ikke noget, og kontrol af alle værdier er obligatorisk.
- Valgssorteringen fungerer ikke godt på store lister
- Andre sorteringsalgoritmer, såsom quicksort, har bedre ydeevne sammenlignet med valgsorteringen.