Selectiesorteeralgoritme met Python Code Voorbeeld

⚡ Slimme samenvatting

Selection Sort is een in-place vergelijkingsalgoritme dat een willekeurige lijst in oplopende volgorde sorteert door herhaaldelijk de kleinste ongesorteerde waarde te selecteren en deze naar het gesorteerde gedeelte te verplaatsen. Deze bron legt uit hoe een selectiesorteeralgoritme werkt. Python voorbeeld en de bijbehorende tijdscomplexiteit.

🎯 Kernidee: Bij selectiesortering wordt herhaaldelijk de minimumwaarde in het ongesorteerde gedeelte gevonden en naar het gesorteerde gedeelte verplaatst.
???? Ter plaatse: Het sorteert met slechts één extra tijdelijke variabele, wat resulteert in een ruimtecomplexiteit van O(1).
Tijdscomplexiteit: Het programma heeft een complexiteit van O(n²) in het slechtste, beste en gemiddelde geval vanwege geneste lussen.
🐍 Python Voorbeeld: Een korte functie met twee lussen verwisselt het minimum op de juiste plaats totdat de lijst gesorteerd is.
Beste gebruik: Het is geschikt voor kleine lijsten waar de transactiekosten laag zijn en elke waarde gecontroleerd moet worden.

Meer informatie

Wat is selectiesortering?

SELECTIE SORT is een vergelijkingssorteeralgoritme dat wordt gebruikt om een willekeurige lijst met items in oplopende volgorde te sorteren. De vergelijking vereist niet veel extra ruimte. Er is slechts één extra geheugenruimte nodig voor de temporele variabele.

Dit staat bekend als in situ sorteren. De selectiesortering heeft een tijdcomplexiteit van O(n²) waarbij n het totale aantal items in de lijst is. De tijdcomplexiteit meet het aantal iteraties dat nodig is om de lijst te sorteren. De lijst is verdeeld in twee partities: de eerste lijst bevat gesorteerde items, terwijl de tweede lijst ongesorteerde items bevat.

Standaard is de gesorteerde lijst leeg en bevat de ongesorteerde lijst alle elementen. De ongesorteerde lijst wordt vervolgens gescand op de minimumwaarde, die vervolgens in de gesorteerde lijst wordt geplaatst. Dit proces wordt herhaald totdat alle waarden zijn vergeleken en gesorteerd.

Hoe werkt selectiesortering?

Het eerste item in de ongesorteerde partitie wordt vergeleken met alle waarden aan de rechterkant om te controleren of dit de minimumwaarde is. Als dit niet de minimumwaarde is, wordt de positie ervan verwisseld met de minimumwaarde.

Voorbeeld

Als de index van de minimumwaarde bijvoorbeeld 3 is, wordt de waarde van het element met index 3 op index 0 geplaatst, terwijl de waarde die op index 0 stond op index 3 wordt geplaatst. Als het eerste element in de ongesorteerde partitie de minimumwaarde, waarna het zijn posities retourneert.
Het element dat als minimumwaarde is bepaald, wordt vervolgens verplaatst naar de partitie aan de linkerkant, de gesorteerde lijst.
De gepartitioneerde zijde heeft nu één element, terwijl de niet-gepartitioneerde zijde (n – 1) elementen heeft waarbij n het totale aantal elementen in de lijst is. Dit proces wordt keer op keer herhaald totdat alle items zijn vergeleken en gesorteerd op basis van hun waarden.

Probleem definitie

Een lijst met elementen die in willekeurige volgorde staan, moet in oplopende volgorde worden gesorteerd. Beschouw de volgende lijst als voorbeeld.

[21,6,9,33,3]

De bovenstaande lijst moet worden gesorteerd om de volgende resultaten te produceren

[3,6,9,21,33]

Oplossing (algoritme)

Stap 1) Haal de waarde van n op, wat de totale grootte van de array is

Stap 2) Verdeel de lijst in gesorteerde en ongesorteerde secties. De gesorteerde sectie is aanvankelijk leeg, terwijl de ongesorteerde sectie de volledige lijst bevat

Stap 3) Kies de minimumwaarde uit de niet-gepartitioneerde sectie en plaats deze in de gesorteerde sectie.

Stap 4) Herhaal het proces (n – 1) keer totdat alle elementen in de lijst zijn gesorteerd.

Visuele weergave

Gegeven een lijst met vijf elementen, illustreren de onderstaande afbeeldingen hoe het selectiesorteeralgoritme door de waarden itereert bij het sorteren ervan.

De volgende afbeelding toont de ongesorteerde lijst

Stap 1)

De eerste waarde 21 wordt vergeleken met de rest van de waarden om te controleren of dit de minimumwaarde is.

3 is de minimumwaarde, dus de posities van 21 en 3 zijn verwisseld. De waarden met een groene achtergrond vertegenwoordigen de gesorteerde partitie van de lijst.

Stap 2)

De waarde 6, het eerste element in de ongesorteerde partitie, wordt vergeleken met de rest van de waarden om erachter te komen of er een lagere waarde bestaat

De waarde 6 is de minimumwaarde en behoudt dus zijn positie.

Stap 3)

Het eerste element van de ongesorteerde lijst met de waarde 9 wordt vergeleken met de rest van de waarden om te controleren of dit de minimumwaarde is.

De waarde 9 is de minimumwaarde en behoudt dus zijn positie in de gesorteerde partitie.

Stap 4)

De waarde 33 wordt vergeleken met de rest van de waarden.

De waarde 21 is lager dan 33, dus de posities worden omgewisseld om de bovenstaande nieuwe lijst te produceren.

Stap 5)

Er is nog maar één waarde over in de niet-gepartitioneerde lijst. Daarom is het al gesorteerd.

De definitieve lijst is zoals weergegeven in de bovenstaande afbeelding.

Selectie Sorteerprogramma met behulp van Python 3

De volgende code toont de implementatie van selectiesortering met behulp van 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))

Als u de bovenstaande code uitvoert, krijgt u de volgende resultaten:

[3, 6, 9, 21, 33]

Code Uitleg

De uitleg voor de code is als volgt

Hier is Code uitleg:

Definieert een functie met de naam selectieSort
Haalt het totale aantal elementen in de lijst op. We hebben dit nodig om het aantal uit te voeren passages te bepalen bij het vergelijken van waarden.
Buitenste lus. Gebruikt de lus om de waarden van de lijst te doorlopen. Het aantal iteraties is (n – 1). De waarde van n is 5, dus (5 – 1) geeft ons 4. Dit betekent dat de buitenste iteraties 4 keer worden uitgevoerd. In elke iteratie wordt de waarde van de variabele i toegewezen aan de variabele minValueIndex
Binnenste lus. Gebruikt de lus om de meest linkse waarde te vergelijken met de andere waarden aan de rechterkant. De waarde voor j begint echter niet bij index 0. Hij begint bij (i + 1). Dit sluit de waarden uit die al zijn gesorteerd, zodat we ons concentreren op items die nog niet zijn gesorteerd.
Zoekt de minimumwaarde in de ongesorteerde lijst en plaatst deze op de juiste positie
Werkt de waarde van minValueIndex bij wanneer de swap plaatsvindt.ping voorwaarde is waar
Vergelijkt de waarden van indexnummers minValueIndex en i om te zien of ze niet gelijk zijn
De meest linkse waarde wordt opgeslagen in een tijdelijke variabele
De lagere waarde vanaf de rechterkant neemt de eerste positie in
De waarde die in de tijdelijke waarde is opgeslagen, wordt opgeslagen op de positie die voorheen werd vastgehouden door de minimumwaarde
Retourneert de gesorteerde lijst als het functieresultaat
Maakt een lijst el met willekeurige getallen
Druk de gesorteerde lijst af nadat u de selectie hebt aangeroepen Sorteerfunctie en el als parameter heeft doorgegeven.

Tijdcomplexiteit van selectiesortering

De sort complexity wordt gebruikt om het aantal uitvoeringstijden uit te drukken dat nodig is om de lijst te sorteren. De implementatie heeft twee lussen.

De buitenste lus, die de waarden één voor één uit de lijst kiest, wordt n keer uitgevoerd, waarbij n het totale aantal waarden in de lijst is.

De binnenste lus, die de waarde uit de buitenste lus vergelijkt met de overige waarden, wordt ook n keer uitgevoerd, waarbij n het totale aantal elementen in de lijst is.

Daarom is het aantal uitvoeringen (n * n), wat ook kan worden uitgedrukt als O(n²).

De selectiesortering kent drie complexiteitscategorieën, namelijk:

Het slechtste geval – hier staat de weergegeven lijst in aflopende volgorde. Het algoritme voert het maximale aantal uitvoeringen uit, uitgedrukt als [Big-O] O(n²)
Beste geval – dit gebeurt wanneer de opgegeven lijst al gesorteerd is. Het algoritme voert het minimale aantal uitvoeringen uit, wat wordt uitgedrukt als [Big-Omega] Ω(n²)
gemiddeld geval – dit gebeurt wanneer de lijst in willekeurige volgorde staat. De gemiddelde complexiteit wordt uitgedrukt als [Big-theta] Θ(n²)

De selectiesorteermethode heeft een ruimtecomplexiteit van O(1), omdat er één tijdelijke variabele nodig is voor de swap-functie.ping waarden.

Wanneer selectiesortering gebruiken?

De selectiesortering kunt u het beste gebruiken als u:

U moet een kleine lijst met items in oplopende volgorde sorteren
Wanneer de kosten van ruilenping de waarde is onbeduidend
Het wordt ook gebruikt als u ervoor wilt zorgen dat alle waarden in de lijst zijn gecontroleerd.

Voordelen van Selectie Sorteren

Hieronder volgen de voordelen van de selectiesortering

Het presteert zeer goed op kleine lijsten
Het is een in-place algoritme. Er is niet veel ruimte nodig om te sorteren. Er is slechts één extra ruimte nodig om de temporele variabele vast te houden.
Het presteert goed op items die al zijn gesorteerd.

Nadelen van selectiesortering

Hieronder staan de nadelen van de selectiesortering.

Het presteert slecht bij het werken aan grote lijsten.
Het aantal iteraties dat tijdens het sorteren wordt gemaakt, is n-kwadraat, waarbij n het totale aantal elementen in de lijst is.
Andere algoritmen, zoals quicksort, presteren beter dan selectiesortering.

Veelgestelde vragen

Selectiesortering is in zijn basisvorm niet stabiel, omdat er sprake is van verwisseling.ping Verre elementen kunnen de relatieve volgorde van gelijke sleutels veranderen. Een variant met een gekoppelde lijst of zorgvuldige verschuivingen kan dit stabiel maken, maar de standaard array-versie is instabiel.

Selectiesortering scant het ongesorteerde deel om het minimum te vinden en vervangt dit, waarbij slechts enkele wisselingen plaatsvinden. Invoegsortering neemt elk element en verschuift grotere gesorteerde elementen naar rechts om het in te voegen. Invoegsortering is doorgaans sneller bij bijna gesorteerde data.

Selectiesortering voert maximaal n-1 wisselingen uit voor een lijst van n elementen, één per doorgang. Dit lage aantal wisselingen maakt het nuttig wanneer schrijven naar het geheugen kostbaar is, hoewel het nog steeds O(n²) vergelijkingen uitvoert.

AI-tutoren kunnen tracDe selectiesorteerprocedure wordt stap voor stap uitgelegd, elke wisseling wordt geanimeerd en je wordt getest op tijdcomplexiteit. Deze interactieve feedback helpt beginners te begrijpen hoe het minimum wordt geselecteerd en verplaatst tijdens elke ronde.

Ja. AI-codeerassistenten kunnen selectiesortering in veel talen genereren, elke regel uitleggen en efficiëntere algoritmen zoals quicksort voorstellen wanneer de invoer groter wordt. Test de gegenereerde code altijd voordat u deze gebruikt.