selection sort c with examples
Een diepgaande blik op selectiesortering in C ++ met voorbeelden.
Zoals de naam zelf suggereert, selecteert de selectiesorteertechniek eerst het kleinste element in de array en verwisselt dit met het eerste element in de array.
Vervolgens verwisselt het het op een na kleinste element in de array met het tweede element enzovoort. Dus voor elke doorgang wordt het kleinste element in de array geselecteerd en op de juiste positie geplaatst totdat de hele array is gesorteerd.
Bekijk hier de perfecte C ++ trainingsgids.
Wat je leert:
- Invoering
- Algemeen algoritme
- Pseudocode voor selectie sorteren
- Illustratie
- C ++ Voorbeeld
- Java-voorbeeld
- Complexiteitsanalyse van selectiesortering
- Gevolgtrekking
- Aanbevolen literatuur
Invoering
Selectie sorteren is een vrij eenvoudige sorteertechniek, aangezien de techniek alleen bestaat uit het vinden van het kleinste element in elke doorgang en het op de juiste positie plaatsen.
Selectie sorteren werkt efficiënt wanneer de lijst die moet worden gesorteerd klein is, maar de prestaties worden slecht beïnvloed naarmate de te sorteren lijst groter wordt.
Daarom kunnen we zeggen dat selectiesortering niet aan te raden is voor grotere lijsten met gegevens.
Algemeen algoritme
Het algemene algoritme voor het sorteren van selecties wordt hieronder gegeven:
gratis testtools voor opnemen en afspelen
Selectie sorteren (A, N)
Stap 1 : Herhaal stap 2 en 3 voor K = 1 tot N-1
Stap 2 : Oproeproutine kleinste (A, K, N, POS)
Stap 3 : Verwissel A [K] met A [POS]
[Einde lus]
Stap 4 : UITGANG
Routine kleinste (A, K, N, POS)
- Stap 1 : [initialize] set smallestElem = A [K]
- Stap 2 : [initialiseren] stel POS = K in
- Stap 3 : voor J = K + 1 tot N -1, herhaal
if smallestElem> A [J]
set smallestElem = A [J]
stel POS = J in
[als einde]
[Einde lus] - Stap 4 : retourneer POS
Pseudocode voor selectie sorteren
Hieronder ziet u een voorbeeld om dit algoritme voor het sorteren van selecties te illustreren.
Illustratie
De tabelweergave voor deze illustratie wordt hieronder weergegeven:
Ongesorteerde lijst | Minste element | Gesorteerde lijst |
---|---|---|
{18,10,7,20,2} | twee | |
{18,10,7,20} | 7 | {twee} |
{18,10,20} | 10 | {2.7} |
{18.20} | 18 | {2,7,10) |
{twintig} | twintig | {2,7,10,18} |
| {2,7,10,18,20} |
Uit de illustratie zien we dat bij elke doorgang het op één na kleinste element op de juiste positie in de gesorteerde array wordt geplaatst. Uit de bovenstaande illustratie zien we dat om een reeks van 5 elementen te sorteren, vier doorgangen nodig waren. Dit betekent in het algemeen dat we, om een reeks van N-elementen te sorteren, in totaal N-1-passen nodig hebben.
Hieronder wordt de implementatie van een selectie-sorteeralgoritme in C ++ gegeven.
C ++ Voorbeeld
Uitgang:
Invoerlijst met te sorteren elementen
11 5 2 20 42 53 23 34101 22
Gesorteerde lijst met elementen is
2 5 11 20 22 23 34 42 53101
Aantal passages vereist om de array te sorteren: 10
Zoals getoond in het bovenstaande programma, beginnen we met het sorteren van selectie door het eerste element in de array te vergelijken met alle andere elementen in de array. Aan het einde van deze vergelijking wordt het kleinste element in de array op de eerste positie geplaatst.
In de volgende doorgang, met dezelfde aanpak, wordt het volgende kleinste element in de array op de juiste positie geplaatst. Dit gaat door tot N elementen, of totdat de hele array is gesorteerd.
Java-voorbeeld
Vervolgens implementeren we de selectiesorteertechniek in de Java-taal.
Uitgang:
Invoerlijst die moet worden gesorteerd ...
11 5 2 20 42 53 23 34101 22
gesorteerde elementen afdrukken ...
2 5 11 20 22 23 34 42 53101
Ook in het bovenstaande Java-voorbeeld passen we dezelfde logica toe. We zoeken herhaaldelijk het kleinste element in de array en plaatsen het in de gesorteerde array totdat de hele array volledig is gesorteerd.
Selectiesortering is dus het eenvoudigste algoritme om te implementeren, omdat we gewoon herhaaldelijk het volgende kleinste element in de array moeten vinden en het moeten verwisselen met het element op de juiste positie.
Complexiteitsanalyse van selectiesortering
Zoals te zien is in de pseudocode hierboven voor selectiesortering, weten we dat selectiesortering twee for-lussen vereist die in elkaar zijn genest om zichzelf te voltooien. Een for-lus doorloopt alle elementen in de array en we vinden de minimale elementindex met een andere for-lus die is genest in de buitenste for-lus.
Daarom, gegeven een grootte N van de invoerarray, heeft het selectiesorteeralgoritme de volgende tijd- en complexiteitswaarden.
Tijdscomplexiteit in het ergste geval | O (n 2); O (n) swaps |
Tijdscomplexiteit in het beste geval | O (n 2); O (n) swaps |
Gemiddelde tijdcomplexiteit | O (n 2); O (n) swaps |
Complexiteit van de ruimte | O (1) |
De tijdcomplexiteit van O ( n twee) komt voornamelijk door het gebruik van twee for-loops. Merk op dat de selectiesorteertechniek nooit meer dan 0 (n) swaps nodig heeft en voordelig is wanneer de geheugenschrijfoperatie kostbaar blijkt te zijn.
Gevolgtrekking
Selectie sorteren is nog een andere eenvoudigste sorteertechniek die gemakkelijk kan worden geïmplementeerd. Selectie sorteren werkt het beste als het bereik van de te sorteren waarden bekend is. Dus wat het sorteren van datastructuren met behulp van selectiesortering betreft, kunnen we alleen datastructuren sorteren die lineair en eindig zijn.
Dit betekent dat we datastructuren zoals arrays efficiënt kunnen sorteren met behulp van de selectie sortering.
In deze tutorial hebben we selectiesortering in detail besproken, inclusief de implementatie van selectiesortering met behulp van C ++ en Java-talen. De logica achter de selectiesortering is om het kleinste element in de lijst herhaaldelijk te vinden en op de juiste positie te plaatsen.
In de volgende tutorial zullen we in detail leren over invoegsortering, waarvan wordt gezegd dat het een efficiëntere techniek is dan de andere twee technieken die we tot nu toe hebben besproken, namelijk bellen- en selectiesortering.
Kijk hier om AZ van C ++ trainingshandleidingen hier te zien.
Aanbevolen literatuur
- Shell-sortering in C ++ met voorbeelden
- MongoDB Sort () -methode met voorbeelden
- Unix-sorteeropdracht met syntaxis, opties en voorbeelden
- Bubbelsortering in C ++ met voorbeelden
- Invoegsortering in C ++ met voorbeelden
- Sorteer samenvoegen in C ++ met voorbeelden
- Heap-sortering in C ++ met voorbeelden
- Snel sorteren in C ++ met voorbeelden