Utvalgssortering: Algoritme forklart med Python Kodeeksempel

Hva er utvalgssortering?

UTVALG SORT er en sammenligningssorteringsalgoritme som brukes til å sortere en tilfeldig liste over elementer i stigende rekkefølge. Sammenligningen krever ikke mye ekstra plass. Det krever bare én ekstra minneplass for den temporale variabelen.

Dette er kjent som på plass sortering. Utvalgssorteringen har en tidskompleksitet på O(n²) hvor n er det totale antallet elementer i listen. Tidskompleksiteten måler antall iterasjoner som kreves for å sortere listen. Listen er delt inn i to partisjoner: Den første listen inneholder sorterte elementer, mens den andre listen inneholder usorterte elementer.

Som standard er den sorterte listen tom, og den usorterte listen inneholder alle elementene. Den usorterte listen skannes deretter for minimumsverdien, som deretter plasseres i den sorterte listen. Denne prosessen gjentas til alle verdiene er sammenlignet og sortert.

Hvordan fungerer utvalgssortering?

Det første elementet i den usorterte partisjonen sammenlignes med alle verdiene til høyre for å sjekke om det er minimumsverdien. Hvis det ikke er minimumsverdien, byttes posisjonen med minimumsverdien.

Eksempel

For eksempel, hvis indeksen for minimumsverdien er 3, plasseres verdien til elementet med indeks 3 ved indeks 0, mens verdien som var på indeks 0 plasseres ved indeks 3. Hvis det første elementet i den usorterte partisjonen er minimumsverdien, så returnerer den sine posisjoner.
Elementet som er bestemt som minimumsverdi flyttes deretter til partisjonen på venstre side, som er den sorterte listen.
Den partisjonerte siden har nå ett element, mens den upartisjonerte siden har (n – 1) elementer hvor n er det totale antallet elementer i listen. Denne prosessen gjentas om og om igjen til alle elementene har blitt sammenlignet og sortert basert på verdiene deres.

Problem Definisjon

En liste over elementer som er i tilfeldig rekkefølge må sorteres i stigende rekkefølge. Tenk på følgende liste som et eksempel.

[21,6,9,33,3]

Listen ovenfor bør sorteres for å gi følgende resultater

[3,6,9,21,33]

Løsning (algoritme)

Trinn 1) Få verdien av n som er den totale størrelsen på matrisen

Trinn 2) Del listen i sorterte og usorterte deler. Den sorterte delen er i utgangspunktet tom mens den usorterte delen inneholder hele listen

Trinn 3) Velg minimumsverdien fra den upartisjonerte delen og plasser den i den sorterte delen.

Trinn 4) Gjenta prosessen (n – 1) ganger til alle elementene i listen er sortert.

Visuell representasjon

Gitt en liste med fem elementer, illustrerer de følgende bildene hvordan algoritmen for utvalgssortering itererer gjennom verdiene når de sorteres.

Følgende bilde viser den usorterte listen

Trinn 1)

Den første verdien 21 sammenlignes med resten av verdiene for å sjekke om det er minimumsverdien.

3 er minimumsverdien, så posisjonene 21 og 3 byttes. Verdiene med grønn bakgrunn representerer den sorterte partisjonen til listen.

Trinn 2)

Verdien 6 som er det første elementet i den usorterte partisjonen sammenlignes med resten av verdiene for å finne ut om en lavere verdi eksisterer

Verdien 6 er minimumsverdien, så den beholder sin posisjon.

Trinn 3)

Det første elementet i den usorterte listen med verdien 9 sammenlignes med resten av verdiene for å sjekke om det er minimumsverdien.

Verdien 9 er minimumsverdien, så den beholder sin posisjon i den sorterte partisjonen.

Trinn 4)

Verdien 33 sammenlignes med resten av verdiene.

Verdien 21 er lavere enn 33, så posisjonene byttes for å produsere den nye listen ovenfor.

Trinn 5)

Vi har bare én verdi igjen i den upartisjonerte listen. Derfor er det allerede sortert.

Den endelige listen er som den som vises i bildet ovenfor.

Utvalg Sorter Program vha Python 3

Følgende kode viser utvalget sorteringsimplementering ved hjelp av 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))

Kjør koden ovenfor gir følgende resultater

[3, 6, 9, 21, 33]

Kode Forklaring

Forklaringen for koden er som følger

Her er kodeforklaring:

Definerer en funksjon kalt selectSort
Henter det totale antallet elementer i listen. Vi trenger dette for å bestemme antall passeringer som skal gjøres når vi sammenligner verdier.
Ytre løkke. Bruker loopen til å iterere gjennom verdiene i listen. Antall iterasjoner er (n – 1). Verdien av n er 5, så (5 – 1) gir oss 4. Dette betyr at de ytre iterasjonene vil bli utført 4 ganger. I hver iterasjon blir verdien av variabelen i tilordnet variabelen minValueIndex
Indre løkke. Bruker loopen til å sammenligne verdien lengst til venstre med de andre verdiene på høyre side. Verdien for j starter imidlertid ikke ved indeks 0. Den starter ved (i + 1). Dette ekskluderer verdiene som allerede er sortert slik at vi fokuserer på varer som ennå ikke er sortert.
Finner minimumsverdien i den usorterte listen og plasserer den i riktig posisjon
Oppdaterer verdien til minValueIndex når byttebetingelsen er sann
Sammenligner verdiene til indekstall minValueIndex og i for å se om de ikke er like
Verdien lengst til venstre lagres i en tidsvariabel
Den nedre verdien fra høyre side tar posisjonen første posisjon
Verdien som ble lagret i den tidsmessige verdien, lagres i posisjonen som tidligere ble holdt av minimumsverdien
Returnerer den sorterte listen som funksjonsresultat
Oppretter en liste el som har tilfeldige tall
Skriv ut den sorterte listen etter å ha kalt utvalget Sorter-funksjonen ved å sende inn el som parameter.

Tidskompleksitet av utvalg Sorter

Sorteringskompleksiteten brukes til å uttrykke antall utførelsestider det tar å sortere listen. Implementeringen har to løkker.

Den ytre løkken som plukker verdiene én etter én fra listen, utføres n ganger hvor n er det totale antallet verdier i listen.

Den indre sløyfen, som sammenligner verdien fra den ytre sløyfen med resten av verdiene, utføres også n ganger hvor n er det totale antallet elementer i listen.

Derfor er antall henrettelser (n * n), som også kan uttrykkes som O(n²).

Utvelgelsessorten har tre kategorier av kompleksitet, nemlig;

I verste fall – det er her den oppgitte listen er i synkende rekkefølge. Algoritmen utfører maksimalt antall henrettelser som er uttrykt som [Big-O] O(n)²)
Beste sak – dette skjer når den angitte listen allerede er sortert. Algoritmen utfører minimum antall henrettelser som er uttrykt som [Big-Omega] ?(n²)
Gjennomsnittlig tilfelle – dette skjer når listen er i tilfeldig rekkefølge. Den gjennomsnittlige kompleksiteten uttrykkes som [Big-theta] ?(n²)

Utvelgelsesorteringen har en romkompleksitet på O(1) da den krever én tidsvariabel som brukes for å bytte verdier.

Når skal du bruke utvalgssortering?

Utvalgssorteringen brukes best når du vil:

Du må sortere en liten liste over elementer i stigende rekkefølge
Når kostnaden ved å bytte verdier er ubetydelig
Den brukes også når du skal forsikre deg om at alle verdiene i listen er sjekket.

Fordeler med utvalgssortering

Følgende er fordelene med utvalgssorten

Den fungerer veldig bra på små lister
Det er en in-place algoritme. Det krever ikke mye plass for sortering. Bare én ekstra plass er nødvendig for å holde den tidsmessige variabelen.
Den fungerer godt på elementer som allerede er sortert.

Ulemper med utvalgssortering

Følgende er ulempene med utvalgssorten.

Den yter dårlig når du jobber med store lister.
Antall iterasjoner gjort under sorteringen er n-kvadrat, hvor n er det totale antallet elementer i listen.
Andre algoritmer, for eksempel quicksort, har bedre ytelse sammenlignet med utvalgssortering.

Sammendrag

Utvalgssortering er en sammenligningsalgoritme på stedet som brukes til å sortere en tilfeldig liste til en ordnet liste. Den har en tidskompleksitet på O(n²)
Listen er delt inn i to deler, sortert og usortert. Minimumsverdien plukkes fra den usorterte delen og plasseres i den sorterte delen.
Dette gjentas til alle varene er sortert.
Implementering av pseudokoden i Python 3 innebærer å bruke to for løkker og if-setninger for å sjekke om bytte er nødvendig
Tidskompleksiteten måler antall trinn som kreves for å sortere listen.
Den verste tidskompleksiteten skjer når listen er i synkende rekkefølge. Den har en tidskompleksitet på [Big-O] O(n²)
Den beste tidskompleksiteten skjer når listen allerede er i stigende rekkefølge. Den har en tidskompleksitet på [Big-Omega] ?(n²)
Den gjennomsnittlige sakstidskompleksiteten skjer når listen er i tilfeldig rekkefølge. Den har en tidskompleksitet på [Big-theta] ?(n²)
Utvalgssorteringen brukes best når du har en liten liste over elementer å sortere, kostnadene ved å bytte verdier spiller ingen rolle, og kontroll av alle verdiene er obligatorisk.
Utvalgssorteringen fungerer ikke bra på store lister
Andre sorteringsalgoritmer, for eksempel quicksort, har bedre ytelse sammenlignet med utvalgssortering.