Vad är urvalssortering?
SELECTION SORT är en jämförelsessorteringsalgoritm som används för att sortera en slumpmässig lista med objekt i stigande ordning. Jämförelsen kräver inte mycket extra utrymme. Det kräver bara ett extra minnesutrymme för den tidsmässiga variabeln.
Detta kallas på plats sortering. Urvalsorteringen har en tidskomplexitet på O (n 2 ) där n är det totala antalet objekt i listan. Tidskomplexiteten mäter antalet iterationer som krävs för att sortera listan. Listan är indelad i två partitioner: Den första listan innehåller sorterade objekt, medan den andra listan innehåller osorterade objekt.
Som standard är den sorterade listan tom och den osorterade listan innehåller alla element. Den osorterade listan skannas sedan efter minimivärdet, som sedan placeras i den sorterade listan. Denna process upprepas tills alla värden har jämförts och sorterats.
I denna algoritmhandledning lär du dig:
- Vad är urvalssortering?
- Hur fungerar urvalssortering?
- Problemdefinition
- Lösning (algoritm)
- Visuell representation
- Selection Sort Program med Python 3
- Kodförklaring
- Tidskomplexitet för urvalssortering
- När ska man välja sortiment?
- Fördelar med urvalssortering
- Nackdelar med urvalssortering
Hur fungerar urvalssortering?
Det första objektet i den osorterade partitionen jämförs med alla värden till höger för att kontrollera om det är minimivärdet. Om det inte är minimivärdet byts dess position med minimivärdet.
Exempel:
- Till exempel, om indexet för minimivärdet är 3, placeras värdet för elementet med index 3 vid index 0 medan värdet som var vid index 0 placeras vid index 3. Om det första elementet i den osorterade partitionen är minimivärdet, sedan returnerar det sina positioner.
- Elementet som har bestämts som minimivärde flyttas sedan till partitionen på vänster sida, som är den sorterade listan.
- Den partitionerade sidan har nu ett element, medan den opartitionerade sidan har (n - 1) element där n är det totala antalet element i listan. Denna process upprepas om och om igen tills alla artiklar har jämförts och sorterats baserat på deras värden.
Problemdefinition
En lista med element som är i slumpmässig ordning måste sorteras i stigande ordning. Tänk på följande lista som ett exempel.
[21,6,9,33,3]
Listan ovan ska sorteras för att ge följande resultat
[3,6,9,21,33]
Lösning (algoritm)
Steg 1) Hämta värdet på n som är arrayens totala storlek
Steg 2) Dela upp listan i sorterade och osorterade sektioner. Det sorterade avsnittet är ursprungligen tomt medan det osorterade avsnittet innehåller hela listan
Steg 3) Välj minimivärdet från det opartitionerade avsnittet och placera det i det sorterade avsnittet.
Steg 4) Upprepa processen (n - 1) gånger tills alla element i listan har sorterats.
Visuell representation
Med en lista med fem element illustrerar följande bilder hur algoritmen för valssortering upprepas genom värdena när de sorteras.
Följande bild visar den osorterade listan
Steg 1)
Det första värdet 21 jämförs med resten av värdena för att kontrollera om det är minimivärdet.
3 är minimivärdet, så positionerna 21 och 3 byts ut. Värdena med en grön bakgrund representerar listans sorterade partition.
Steg 2)
Värdet 6 som är det första elementet i den osorterade partitionen jämförs med resten av värdena för att ta reda på om det finns ett lägre värde
Värdet 6 är minimivärdet, så det behåller sin position.
Steg 3)
Det första elementet i den osorterade listan med värdet 9 jämförs med resten av värdena för att kontrollera om det är minimivärdet.
Värdet 9 är minimivärdet så att det bibehåller sin position i den sorterade partitionen.
Steg 4)
Värdet 33 jämförs med resten av värdena.
Värdet 21 är lägre än 33, så positionerna byts ut för att producera ovanstående nya lista.
Steg 5)
Vi har bara ett värde kvar i den opartitionerade listan. Därför är det redan sorterat.
Den sista listan är som den som visas i bilden ovan.
Selection Sort Program med Python 3
Följande kod visar implementeringen av sorteringssorter med 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 ovanstående kod ger följande resultat
[3, 6, 9, 21, 33]
Kodförklaring
Förklaringen till koden är som följer
Här är kodförklaring:
- Definierar en funktion med namnet selectionSort
- Hämtar det totala antalet element i listan. Vi behöver detta för att bestämma antalet pass som ska göras när man jämför värden.
- Yttre ögla. Använder slingan för att upprepa genom värdena i listan. Antalet iterationer är (n - 1). Värdet på n är 5, så (5 - 1) ger oss 4. Detta innebär att de yttre iterationerna kommer att utföras fyra gånger. I varje iteration tilldelas variabeln i variabeln minValueIndex
- Inre slinga. Använder slingan för att jämföra värdet längst till vänster med de andra värdena på höger sida. Värdet för j börjar dock inte vid index 0. Det börjar vid (i + 1). Detta exkluderar de värden som redan har sorterats så att vi fokuserar på objekt som ännu inte har sorterats.
- Hitta minimivärdet i den osorterade listan och placerar det i rätt position
- Uppdaterar värdet på minValueIndex när utbytesvillkoret är sant
- Jämför indexvärdena minValueIndex och i för att se om de inte är lika
- Värdet längst till vänster lagras i en tidsvariabel
- Det lägre värdet från höger sida tar positionen som första position
- Värdet som lagrades i det tidsmässiga värdet lagras i den position som tidigare innehades av minimivärdet
- Returnerar den sorterade listan som funktionsresultat
- Skapar en lista med slumpmässiga siffror
- Skriv ut den sorterade listan efter att ha anropat valet Sorteringsfunktion som skickas in som parameter.
Tidskomplexitet för urvalssortering
Sorteringskomplexiteten används för att uttrycka antalet exekveringstider som det tar att sortera listan. Implementeringen har två slingor.
Den yttre slingan som plockar värdena en efter en från listan körs n gånger där n är det totala antalet värden i listan.
Den inre slingan, som jämför värdet från den yttre slingan med resten av värdena, körs också n gånger där n är det totala antalet element i listan.
Därför är antalet avrättningar (n * n), vilket också kan uttryckas som O (n 2 ).
Urvalssorten har tre kategorier av komplexitet, nämligen;
- Värsta fall - det är här listan i fallande ordning. Algoritmen utför det maximala antalet körningar som uttrycks som [Big-O] O (n 2 )
- I bästa fall - detta inträffar när den angivna listan redan är sorterad. Algoritmen utför det minsta antalet exekveringar som uttrycks som [Big-Omega] Ω (n 2 )
- Genomsnittligt fall - detta inträffar när listan är i slumpmässig ordning. Den genomsnittliga komplexiteten uttrycks som [Big-theta] ⊝ (n 2 )
Urvalsorteringen har en rymdkomplexitet på O (1) eftersom den kräver en tidsvariabel som används för att byta värden.
När ska man välja sortiment?
Urvalssorten används bäst när du vill:
- Du måste sortera en liten lista med objekt i stigande ordning
- När kostnaden för att byta värden är obetydlig
- Den används också när du behöver se till att alla värden i listan har kontrollerats.
Fördelar med urvalssortering
Följande är fördelarna med urvalsorteringen
- Det fungerar mycket bra på små listor
- Det är en platsalgoritm. Det kräver inte mycket utrymme för sortering. Endast ett extra utrymme krävs för att hålla den temporala variabeln.
- Det fungerar bra på objekt som redan har sorterats.
Nackdelar med urvalssortering
Följande är nackdelarna med urvalsorteringen.
- Det fungerar dåligt när man arbetar på stora listor.
- Antalet iterationer som gjorts under sorteringen är n-kvadrat, där n är det totala antalet element i listan.
- Andra algoritmer, som quicksort, har bättre prestanda jämfört med urvalssorten.
Sammanfattning:
- Urvalsortering är en platsjämförelsealgoritm som används för att sortera en slumpmässig lista i en ordnad lista. Den har en tidskomplexitet av O (n 2 )
- Listan är indelad i två sektioner, sorterade och osorterade. Minimivärdet väljs från det osorterade avsnittet och placeras i det sorterade avsnittet.
- Denna sak upprepas tills alla objekt har sorterats.
- Implementering av pseudokoden i Python 3 innebär att man använder två för slingor och om uttalanden för att kontrollera om byte är nödvändig
- Tidskomplexiteten mäter antalet steg som krävs för att sortera listan.
- Det värsta fallets tidskomplexitet händer när listan är i fallande ordning. Den har en tidskomplexitet av [Big-O] O (n 2 )
- Bästa tidskomplexitet händer när listan redan är i stigande ordning. Den har en tidskomplexitet på [Big-Omega] Ω (n 2 )
- Den genomsnittliga fallkomplexiteten händer när listan är i slumpmässig ordning. Den har en tidskomplexitet av [Big-theta] ⊝ (n 2 )
- Valssorteringen används bäst när du har en liten lista med objekt att sortera, kostnaden för att byta värden spelar ingen roll och det är obligatoriskt att kontrollera alla värden.
- Urvalssorten fungerar inte bra på stora listor
- Andra sorteringsalgoritmer, som quicksort, har bättre prestanda jämfört med urvalsorteringen.