Valgsortering: Algoritme forklart med Python-kodeeksempel

Innholdsfortegnelse:

Anonim

Hva er Selection Sort?

SELECTION 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 ett ekstra minne for den tidsmessige variabelen.

Dette er kjent som stedlig sortering. Valgsorteringen har en tidskompleksitet på O (n 2 ) der 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 blitt sammenlignet og sortert.

I denne algoritmeopplæringen lærer du:

  • Hva er Selection Sort?
  • Hvordan fungerer valgsortering?
  • Problemdefinisjon
  • Løsning (algoritme)
  • Visuell representasjon
  • Selection Sort Program ved hjelp av Python 3
  • Kode Forklaring
  • Tidskompleksitet av utvalgssortering
  • Når skal du velge utvalgssortering?
  • Fordeler med utvalgssortering
  • Ulemper ved utvalgssortering

Hvordan fungerer valgsortering?

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 ut med minimumsverdien.

Eksempel:

  • Hvis for eksempel indeksen til minimumsverdien er 3, plasseres verdien av elementet med indeks 3 til indeks 0 mens verdien som var ved indeks 0 er plassert i 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 ikke-partisjonerte siden har (n - 1) elementer der n er det totale antallet elementer i listen. Denne prosessen gjentas igjen og igjen til alle elementene er blitt sammenlignet og sortert basert på deres verdier.

Problemdefinisjon

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

[21,6,9,33,3]

Listen over skal 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 seksjoner. Den sorterte delen er først tom mens den usorterte delen inneholder hele listen

Trinn 3) Velg minimumsverdien fra den ikke-partisjonerte 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 over fem elementer, illustrerer følgende bilder hvordan valgsorteringsalgoritmen gjentar seg gjennom verdiene når du sorterer dem.

Følgende bilde viser den usorterte listen

Trinn 1)

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

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

Steg 2)

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

Verdien 6 er minimumsverdien, så den opprettholder 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 opprettholder 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 en verdi igjen i den ikke-partisjonerte listen. Derfor er den allerede sortert.

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

Selection Sort Program ved hjelp av Python 3

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

Kjør koden ovenfor gir følgende resultater

[3, 6, 9, 21, 33]

Kode Forklaring

Forklaringen på koden er som følger

Her er kodeforklaring:

  1. Definerer en funksjon som heter selectionSort
  2. Får det totale antallet elementer i listen. Vi trenger dette for å bestemme antall passeringer som skal foretas når vi sammenligner verdier.
  3. Ytre løkke. Bruker løkken for å gjenta 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 gjentakelsene vil bli utført 4 ganger. I hver iterasjon tildeles verdien av variabelen i variabelen minValueIndex
  4. Indre sløyfe. Bruker løkken for å 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 av minValueIndex når byttetilstanden er oppfylt
  7. Sammenligner verdiene til indeksnummer minValueIndex og i for å se om de ikke er like
  8. Verdien lengst til venstre er lagret i en tidsvariabel
  9. Den lavere verdien fra høyre side inntar førsteplasseringen
  10. Verdien som ble lagret i tidsverdien lagres i posisjonen som tidligere ble holdt av minimumsverdien
  11. Returnerer den sorterte listen som funksjonsresultat
  12. Oppretter en listeel som har tilfeldige tall
  13. Skriv ut den sorterte listen etter at du har kalt utvalget Sorteringsfunksjonen passerer i el som parameter.

Tidskompleksitet av utvalgssortering

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

Den ytre sløyfen som plukker verdiene en etter en fra listen, utføres n ganger der n er det totale antallet verdier i listen.

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

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

Utvalgssorten har tre kategorier av kompleksitet, nemlig;

  • Verste tilfelle - det er her listen som er oppgitt er i synkende rekkefølge. Algoritmen utfører det maksimale antall utførelser som er uttrykt som [Big-O] O (n 2 )
  • I beste fall - dette skjer når den angitte listen allerede er sortert. Algoritmen utfører det minste antall henrettelser som er uttrykt som [Big-Omega] Ω (n 2 )
  • Gjennomsnittlig tilfelle - dette skjer når listen er i tilfeldig rekkefølge. Gjennomsnittlig kompleksitet uttrykkes som [Big-theta] ⊝ (n 2 )

Valgsorteringen har en romkompleksitet på O (1), da den krever en tidsvariabel som brukes for å bytte verdier.

Når skal du velge utvalgssortering?

Valgsorteringen brukes best når du vil:

  • Du må sortere en liten liste over varer i stigende rekkefølge
  • Når kostnaden for å bytte verdier er ubetydelig
  • Den brukes også når du må sørge for at alle verdiene i listen er sjekket.

Fordeler med utvalgssortering

Følgende er fordelene med utvalgssorteringen

  • Det fungerer veldig bra på små lister
  • Det er en på plass algoritme. Det krever ikke mye plass for sortering. Bare en ekstra plass er nødvendig for å holde tidsvariabelen.
  • Det fungerer bra på varer som allerede er sortert.

Ulemper ved utvalgssortering

Følgende er ulempene ved utvalget.

  • Det fungerer dårlig når du jobber med store lister.
  • Antall gjentakelser som er 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 utvalget.

Sammendrag:

  • Valgsortering er en stedlig sammenligningsalgoritme som brukes til å sortere en tilfeldig liste i en ordnet liste. Den har en tidskompleksitet på O (n 2 )
  • Listen er delt inn i to seksjoner, sortert og usortert. Minimumsverdien plukkes fra den usorterte delen og plasseres i den sorterte delen.
  • Denne tingen gjentas til alle elementene er sortert.
  • Implementering av pseudokoden i Python 3 innebærer å bruke to for løkker og om uttalelser for å sjekke om bytte er nødvendig
  • Tidskompleksiteten måler antall trinn som kreves for å sortere listen.
  • Verst mulig tidskompleksitet skjer når listen er i fallende rekkefølge. Den har en tidskompleksitet på [Big-O] O (n 2 )
  • Beste tidskompleksitet skjer når listen allerede er i stigende rekkefølge. Den har en tidskompleksitet på [Big-Omega] Ω (n 2 )
  • Gjennomsnittlig tidskompleksitet skjer når listen er i tilfeldig rekkefølge. Den har en tidskompleksitet på [Big-theta] ⊝ (n 2 )
  • Valgssorteringen brukes best når du har en liten liste over varer å sortere, kostnaden for å bytte verdier spiller ingen rolle, og det er obligatorisk å kontrollere alle verdiene.
  • Utvalget sorterer ikke bra på store lister
  • Andre sorteringsalgoritmer, for eksempel quicksort, har bedre ytelse sammenlignet med valgsorteringen.