Wat is Selectie sorteren?
SELECTIE SORTEREN is een vergelijkingssorteeralgoritme dat wordt gebruikt om een willekeurige lijst met items in oplopende volgorde te sorteren. De vergelijking vereist niet veel extra ruimte. Het vereist slechts één extra geheugenruimte voor de tijdelijke variabele.
Dit staat bekend als in-place sorteren. De selectiesortering heeft een tijdcomplexiteit van O (n 2 ), 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 onderverdeeld 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.
In deze Algoritme-zelfstudie leert u:
- Wat is Selectie sorteren?
- Hoe werkt selectiesortering?
- Probleem definitie
- Oplossing (algoritme)
- Visuele representatie
- Selectie Sorteerprogramma met Python 3
- Code Verklaring
- Tijdscomplexiteit van selectie sorteren
- Wanneer selectiesortering gebruiken?
- Voordelen van selectiesortering
- Nadelen van selectiesortering
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 het niet de minimumwaarde is, wordt zijn positie omgewisseld 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 is de minimumwaarde, dan geeft het zijn posities terug.
- 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) Verkrijg de waarde van n, de totale grootte van de array
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 representatie
Gegeven een lijst van vijf elementen, illustreren de volgende afbeeldingen hoe het selectie-sorteeralgoritme de waarden doorloopt 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 worden omgewisseld. 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, dus deze behoudt 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, dus het behoudt 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)
We hebben nog maar één waarde over in de niet-gepartitioneerde lijst. Daarom is het al gesorteerd.
De uiteindelijke lijst is zoals weergegeven in de bovenstaande afbeelding.
Selectie Sorteerprogramma met Python 3
De volgende code toont de implementatie van de selectie-sortering met 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))
Voer de bovenstaande code uit, levert de volgende resultaten op
[3, 6, 9, 21, 33]
Code Verklaring
De verklaring voor de code is als volgt
Hier is de code-uitleg:
- Definieert een functie met de naam selectionSort
- Haalt het totale aantal elementen in de lijst op. We hebben dit nodig om het aantal passages te bepalen dat moet worden gemaakt 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. Bij 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. Het begint bij (i + 1). Dit is exclusief de waarden die al zijn gesorteerd, zodat we ons concentreren op items die nog niet zijn gesorteerd.
- Vindt de minimumwaarde in de ongesorteerde lijst en plaatst deze op de juiste positie
- Werkt de waarde van minValueIndex bij wanneer de wisselvoorwaarde waar is
- 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 onderste waarde vanaf de rechterkant neemt de positie eerste positie in
- De waarde die is opgeslagen in de tijdelijke waarde, wordt opgeslagen op de positie die voorheen werd vastgehouden door de minimumwaarde
- Retourneert de gesorteerde lijst als het functieresultaat
- Creëert een lijst el met willekeurige getallen
- Druk de gesorteerde lijst af na het aanroepen van de functie Selectie Sorteren door el als parameter door te geven.
Tijdscomplexiteit van selectie sorteren
De sorteercomplexiteit wordt gebruikt om het aantal uitvoeringstijden uit te drukken dat nodig is om de lijst te sorteren. De implementatie heeft twee loops.
De buitenste lus die de waarden een voor een uit de lijst kiest, wordt n keer uitgevoerd, waarbij n het totale aantal waarden in de lijst is.
De binnenste lus, die de waarde van de buitenste lus vergelijkt met de rest van de 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 2 ).
De selectiesoort heeft drie categorieën van complexiteit, namelijk;
- In het ergste geval - dit is waar de verstrekte lijst in aflopende volgorde staat. Het algoritme voert het maximale aantal uitvoeringen uit dat wordt uitgedrukt als [Big-O] O (n 2 )
- In het beste geval - dit gebeurt wanneer de verstrekte lijst al is gesorteerd. Het algoritme voert het minimum aantal uitvoeringen uit dat wordt uitgedrukt als [Big-Omega] Ω (n 2 )
- Gemiddeld geval - dit gebeurt wanneer de lijst in willekeurige volgorde staat. De gemiddelde complexiteit wordt uitgedrukt als [Big-theta] ⊝ (n 2 )
De selectiesortering heeft een ruimtecomplexiteit van O (1) omdat er één tijdelijke variabele nodig is die wordt gebruikt voor het omwisselen van waarden.
Wanneer selectiesortering gebruiken?
De selectiesortering kan het beste worden gebruikt als u:
- U moet een kleine lijst met items in oplopende volgorde sorteren
- Wanneer de kosten van het ruilen van waarden onbeduidend zijn
- Het wordt ook gebruikt als u ervoor moet zorgen dat alle waarden in de lijst zijn gecontroleerd.
Voordelen van selectiesortering
Hieronder volgen de voordelen van de selectiesortering
- Het presteert erg goed op kleine lijsten
- Het is een in-place algoritme. Het heeft niet veel ruimte nodig om te sorteren. Er is slechts één extra spatie nodig om de temporele variabele vast te houden.
- Het presteert goed op items die al zijn gesorteerd.
Nadelen van selectiesortering
Hieronder volgen de nadelen van de selectiesortering.
- Het presteert slecht bij het werken aan enorme lijsten.
- Het aantal iteraties tijdens het sorteren is n-kwadraat, waarbij n het totale aantal elementen in de lijst is.
- Andere algoritmen, zoals quicksort, presteren beter in vergelijking met de selectiesortering.
Overzicht:
- Selectie sorteren is een in-place vergelijkingsalgoritme dat wordt gebruikt om een willekeurige lijst in een geordende lijst te sorteren. Het heeft een tijdcomplexiteit van O (n 2 )
- De lijst is onderverdeeld in twee secties, gesorteerd en ongesorteerd. De minimumwaarde wordt uit de ongesorteerde sectie gehaald en in de gesorteerde sectie geplaatst.
- Dit ding wordt herhaald totdat alle items zijn gesorteerd.
- Het implementeren van de pseudocode in Python 3 omvat het gebruik van twee for-lussen en als instructies om te controleren of swapping nodig is
- De tijdcomplexiteit meet het aantal stappen dat nodig is om de lijst te sorteren.
- De moeilijkste tijdcomplexiteit doet zich voor wanneer de lijst in aflopende volgorde staat. Het heeft een tijdcomplexiteit van [Big-O] O (n 2 )
- De beste tijdcomplexiteit doet zich voor wanneer de lijst al in oplopende volgorde staat. Het heeft een tijdcomplexiteit van [Big-Omega] Ω (n 2 )
- De gemiddelde tijdcomplexiteit treedt op wanneer de lijst in willekeurige volgorde staat. Het heeft een tijdcomplexiteit van [Big-theta] ⊝ (n 2 )
- De selectiesortering kan het beste worden gebruikt als u een kleine lijst met items hebt om te sorteren, de kosten van het omwisselen van waarden er niet toe doen en het controleren van alle waarden verplicht is.
- De selectiesortering presteert niet goed op grote lijsten
- Andere sorteeralgoritmen, zoals quicksort, presteren beter in vergelijking met de selectiesortering.