Urval Sortera: Algoritm förklaras med Python Kodsexempel

Vad är urvalssortering?

URVAL SORT är en jämförelsesorteringsalgoritm 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 temporala variabeln.

Detta kallas på plats sortering. Urvalssorteringen har en tidskomplexitet på O(n²) 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 uppdelad 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.

Hur fungerar urvalssorteringen?

Den första posten 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 mot minimivärdet.

Exempelvis

• Till exempel, om indexet för minimivärdet är 3, så placeras värdet på 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 lägsta värdet, sedan returnerar den 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 objekt har jämförts och sorterats utifrån deras värden.

Problem Definition

En lista med element som är i slumpmässig ordning måste sorteras i stigande ordning. Betrakta följande lista som ett exempel.

[21,6,9,33,3]

Listan ovan bör sorteras för att ge följande resultat

[3,6,9,21,33]

Lösning (algoritm)

Steg 1) Få värdet på n som är den totala storleken på arrayen

Steg 2) Dela upp listan i sorterade och osorterade sektioner. Det sorterade avsnittet är initialt tomt medan det osorterade avsnittet innehåller hela listan

Steg 3) Välj minimivärdet från den opartitionerade sektionen och placera den i den sorterade sektionen.

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 urvalssorteringsalgoritmen itererar 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 om. Värdena med grön bakgrund representerar den sorterade partitionen i listan.

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 ett lägre värde finns

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å det behå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 om för att skapa den nya listan ovan.

Steg 5)

Vi har bara ett värde kvar i den opartitionerade listan. Därför är det redan sorterat.

Den slutliga listan är som den som visas i bilden ovan.

Val Sortera Program med hjälp av Python 3

Följande kod visar implementeringen av urvalssorteringen med hjälp 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))

Kör koden ovan ger följande resultat

[3, 6, 9, 21, 33]

Kodförklaring

Förklaringen till koden är följande

Här är kodförklaringen:

1. Definierar en funktion som heter selectSort
2. 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 vi jämför värden.
3. Yttre slinga. Använder loopen för att iterera genom värdena i listan. Antalet iterationer är (n – 1). Värdet på n är 5, så (5 – 1) ger oss 4. Det betyder att de yttre iterationerna kommer att utföras 4 gånger. I varje iteration tilldelas värdet av variabeln i variabeln minValueIndex
4. Inre slinga. Använder loopen 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å artiklar som ännu inte har sorterats.
5. Hittar minimivärdet i den osorterade listan och placerar det på rätt plats
6. Uppdaterar värdet för minValueIndex när bytesvillkoret är sant
7. Jämför värdena för indexnummer minValueIndex och i för att se om de inte är lika
8. Värdet längst till vänster lagras i en tidsvariabel
9. Det lägre värdet från höger sida tar positionens första position
10. Värdet som lagrades i det tidsmässiga värdet lagras i den position som tidigare hölls av minimivärdet
11. Returnerar den sorterade listan som funktionsresultat
12. Skapar en lista el som har slumptal
13. Skriv ut den sorterade listan efter att ha anropat urvalet Sorteringsfunktionen och skickar in el som parameter.

Tidskomplexitet Urval Sortera

Sorteringskomplexiteten används för att uttrycka antalet körningstider det tar att sortera listan. Implementeringen har två loopar.

Den yttre slingan som väljer värdena ett efter ett från listan exekveras 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, exekveras 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²).

Urvalssorten har tre kategorier av komplexitet nämligen;

• Värsta fall – det är här listan som tillhandahålls är i fallande ordning. Algoritmen utför det maximala antalet exekveringar som uttrycks som [Big-O] O(n)²)
• Bästa fall – detta inträffar när den tillhandahållna listan redan är sorterad. Algoritmen utför det minsta antalet exekveringar som uttrycks som [Big-Omega] ?(n²)
• Genomsnittligt fall – detta inträffar när listan är i slumpmässig ordning. Den genomsnittliga komplexiteten uttrycks som [Big-theta] ?(n²)

Urvalssorteringen 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 använda urvalssortering?

Urvalssorteringen 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 försäkra dig om att alla värden i listan har kontrollerats.

Fördelar med urvalssortering

Följande är fördelarna med urvalssorten

• Den fungerar mycket bra på små listor
• Det är en på plats algoritm. 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 urvalssorten.

• Den presterar dåligt när man arbetar med stora listor.
• Antalet iterationer som görs under sorteringen är n-kvadrat, där n är det totala antalet element i listan.
• Andra algoritmer, såsom quicksort, har bättre prestanda jämfört med urvalssorteringen.

Sammanfattning

• Urvalssortering är en jämförelsealgoritm på plats som används för att sortera en slumpmässig lista till en ordnad lista. Den har en tidskomplexitet av O(n²)
• Listan är uppdelad i två avsnitt, sorterade och osorterade. Minimivärdet plockas från den osorterade sektionen och placeras i den sorterade sektionen.
• Detta upprepas tills alla objekt har sorterats.
• Implementering av pseudokoden i Python 3 innebär att man använder två för loopar och if-satser för att kontrollera om byte är nödvändig
• Tidskomplexiteten mäter antalet steg som krävs för att sortera listan.
• Den värsta tidskomplexiteten inträffar när listan är i fallande ordning. Den har en tidskomplexitet på [Big-O] O(n²)
• Den bästa möjliga tidskomplexiteten inträffar när listan redan är i stigande ordning. Den har en tidskomplexitet av [Big-Omega] ?(n²)
• Den genomsnittliga tidskomplexiteten i fallet inträffar när listan är i slumpmässig ordning. Den har en tidskomplexitet av [Big-theta] ?(n²)
• Urvalssorteringen 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 kontroll av alla värden är obligatorisk.
• Urvalssorteringen fungerar inte bra på enorma listor
• Andra sorteringsalgoritmer, till exempel quicksort, har bättre prestanda jämfört med urvalssorteringen.