selection sort java selection sort algorithm examples
In deze zelfstudie wordt alles uitgelegd over selectiesortering in Java, samen met selectiesorteeralgoritme, Java-code, implementatie in Java en Java-voorbeelden:
De selectiesorteertechniek is een methode waarbij het kleinste element in de array wordt geselecteerd en verwisseld met het eerste element van de array. Vervolgens wordt het op een na kleinste element in de array verwisseld met het tweede element en vice versa.
Kijk hier om AZ van Java-trainingshandleidingen hier te zien.
Wat je leert:
Selectie sorteren in Java
Op deze manier wordt het kleinste element in de array herhaaldelijk geselecteerd en op de juiste positie geplaatst totdat de hele array is gesorteerd.
Er worden twee sub-arrays onderhouden voor het sorteren van selecties:
- Gesorteerde subarray: Bij elke iteratie wordt het minimumelement gevonden en op de juiste positie geplaatst. Deze submatrix is gesorteerd.
- Ongesorteerde subarray: De overige elementen die niet zijn gesorteerd.
De selectiesortering is een eenvoudige en gemakkelijke sorteertechniek. De techniek omvat alleen het vinden van het kleinste element in elke gang en het op de juiste positie plaatsen. De selectiesortering is ideaal voor kleinere gegevenssets, aangezien de kleinere gegevensset efficiënt wordt gesorteerd.
We kunnen dus zeggen dat selectiesortering niet aan te raden is voor grotere lijsten met gegevens.
Selectie sorteeralgoritme
Het algemene algoritme voor selectiesortering wordt hieronder gegeven:
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 : [initialiseren] set smallestItem = A [K]
Stap 2 : [initialiseren] stel POS = K in
Stap 3
voor J = K + 1 tot N -1, herhaal
if smallestItem> A [J]
set smallestItem = A [J]
stel POS = J in
[als einde]
[Einde lus]
Stap 4 : retourneer POS
Zoals u kunt zien, wordt de routine om het kleinste nummer te vinden aangeroepen tijdens het doorlopen van de dataset. Zodra het kleinste element is gevonden, wordt het op de gewenste positie geplaatst.
oops concepten in c # met voorbeelden voor ervaren
Pseudocode voor selectie sorteren
De pseudo-code voor het selectie-sorteeralgoritme wordt hieronder gegeven.
Laten we nu het sorteren van een array illustreren met behulp van selectiesortering.
Selectie Sorteervoorbeeld
Beschouw de volgende array die moet worden gesorteerd als een voorbeeld van een selectiesortering.
Hieronder vindt u een tabelweergave ter illustratie:
Ongesorteerde lijst | Minste element | Gesorteerde lijst |
---|---|---|
{17,10,7,29,2} | twee | |
{17,10,7,29} | 7 | {twee} |
{17,10,29} | 10 | {2.7} |
{17,29} | 17 | {2,7,10) |
{29} | 29 | {2,7,10,17} |
| {2,7,10,17,29} |
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. Over het algemeen hebben we in totaal N-1-passen nodig om een array van N-elementen te sorteren.
Selectie sorteren implementatie in Java
Laten we nu het Java-programma demonstreren om selectiesortering te implementeren.
Uitgang:
Oorspronkelijke matrix: [7, 5, 2, 20, 42, 15, 23, 34, 10]
Gesorteerde matrix: [2, 5, 7, 10, 15, 20, 23, 34, 42]
In het bovenstaande Java-voorbeeld vinden we herhaaldelijk het kleinste element in de array en plaatsen het in de gesorteerde array totdat de hele array volledig is gesorteerd.
Selectie Sorteer gekoppelde lijst in Java
Hieronder is een gelinkte lijst weergegeven en we moeten deze sorteren met behulp van selectiesortering. Om dit te doen zullen we de recursieve benadering van selectiesortering gebruiken. In plaats van het gegevensgedeelte van het knooppunt om te wisselen, zullen we de knooppunten omwisselen en de wijzers opnieuw uitlijnen.
wat is een goede gratis firewall voor Windows 7 64-bit?
Dus als de gekoppelde lijst als volgt wordt weergegeven:
Hieronder wordt het Java-programma weergegeven dat de bovenstaande sortering implementeert.
Uitgang:
Oorspronkelijke gekoppelde lijst:
7 9 3 5 1 11
Gekoppelde lijst na sortering:
1 3 5 7 9 11
Merk op dat we in het bovenstaande programma de links van de knooppunten opnieuw hebben uitgelijnd in plaats van alleen de gegevenscomponent van het knooppunt te sorteren.
Veel Gestelde Vragen
V # 1) Hoe werkt Selectie sorteren?
Antwoord: Selectie sorteren werkt door twee sub-arrays te behouden. Het minimumelement uit de ongesorteerde subarray wordt op de juiste positie in een gesorteerde subarray geplaatst. Vervolgens wordt het op een na laagste element op de juiste positie geplaatst. Op deze manier wordt de hele array gesorteerd door tijdens elke iteratie een minimumelement te selecteren.
Vraag 2 Wat is de complexiteit van de selectie-sortering?
Antwoord: De algehele complexiteit van het selecteren van een sortering is O (ntwee), waardoor het het algoritme is dat inefficiënt is op grotere gegevenssets. Andere sorteertechnieken zijn efficiënter.
Vraag 3 Wat zijn de voor- en nadelen van selectiesortering?
Antwoord: Selectie sorteren is de in-place sorteertechniek en vereist dus geen extra opslag om tussenelementen op te slaan.
Het werkt efficiënt op kleinere datastructuren en op de datasets die bijna gesorteerd zijn.
Het grootste nadeel van de selectiesorteertechniek is dat deze zeer slecht presteert naarmate de omvang van de datastructuur toeneemt. Het wordt niet alleen langzamer, maar vermindert ook de efficiëntie.
Vraag 4 Hoeveel swaps zijn er in de selectie-sortering?
Antwoord: De selectiesorteertechniek vereist het minimum aantal swaps. In het beste geval, wanneer de array is gesorteerd, is het aantal swaps in de selectiesortering 0.
Vraag 5 Is selectie sneller dan sorteren met invoeging?
Antwoord: Invoegsortering is sneller, efficiënter en stabieler. Selectie sorteren is alleen sneller voor kleinere gegevenssets en gedeeltelijk gesorteerde structuren.
Gevolgtrekking
Selectie sorteren is een techniek die werkt door het minimumelement te selecteren tijdens het doorlopen van de array. Voor elke pass / iteratie wordt het volgende minimumelement in de dataset geselecteerd en op de juiste positie geplaatst.
De selectiesorteertechniek werkt efficiënt wanneer het aantal elementen in de dataset kleiner is, maar begint slecht te presteren naarmate de omvang van de dataset toeneemt. Het wordt inefficiënt in vergelijking met andere vergelijkbare technieken zoals invoegsortering.
In deze zelfstudie hebben we voorbeelden geïmplementeerd om arrays en gekoppelde lijsten te sorteren met behulp van selectiesortering.
Bezoek hier om de Java-trainingsserie voor iedereen te zien.
Aanbevolen literatuur
- Hoe een array in Java te sorteren - Tutorial met voorbeelden
- Selectie sorteren in C ++ met voorbeelden
- Zelfstudie over Java-array-lengte met codevoorbeelden
- MongoDB Sort () -methode met voorbeelden
- Jagged Array in Java - Tutorial met voorbeelden
- Unix-sorteeropdracht met syntaxis, opties en voorbeelden
- Keer een array in Java om - 3 methoden met voorbeelden
- JAVA-zelfstudie voor beginners: 100+ praktische Java-videotutorials