Sorteringsalgoritme for utvalg med Python Code Eksempel

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]

Code Forklaring

Forklaringen for koden er som følger

Her er Code forklaring:

1. Definerer en funksjon kalt selectSort
2. Henter det totale antallet elementer i listen. Vi trenger dette for å bestemme antall passeringer som skal gjøres når vi sammenligner verdier.
3. 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
4. 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.
5. Finner minimumsverdien i den usorterte listen og plasserer den i riktig posisjon
6. Oppdaterer verdien til minValueIndex når byttetping betingelsen er sann
7. Sammenligner verdiene til indekstall minValueIndex og i for å se om de ikke er like
8. Verdien lengst til venstre lagres i en tidsvariabel
9. Den nedre verdien fra høyre side tar posisjonen første posisjon
10. Verdien som ble lagret i den tidsmessige verdien, lagres i posisjonen som tidligere ble holdt av minimumsverdien
11. Returnerer den sorterte listen som funksjonsresultat
12. Oppretter en liste el som har tilfeldige tall
13. 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 oppgitte listen allerede er sortert. Algoritmen utfører minimum antall utførelser, som uttrykkes som [Big-Omega] Ω(n²)
• Gjennomsnittlig tilfelle – dette skjer når listen er i tilfeldig rekkefølge. Den gjennomsnittlige kompleksiteten uttrykkes som [Big-theta] Θ(n²)

Utvalgssorteringen har en romkompleksitet på O(1) ettersom den krever én temporal variabel som brukes til bytteping 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 for byttetping verdier er ubetydelige
• 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.

Spørsmål og svar