streamalism.org

1. Inleiding

In deze tutorial zullen we leer Selectie sorteren, bekijk de implementatie ervan in Java en analyseer de prestaties.

2. Algoritme overzicht

Selectie sorteren begint met het element in de 1e positie van een ongesorteerde array en scant door de volgende elementen naar vind het kleinste element. Eenmaal gevonden, wordt het kleinste element verwisseld met het element in de eerste positie.

Het algoritme gaat dan verder naar het element op de 2e positie en scant door de volgende elementen om de index van het 2e kleinste element te vinden. Eenmaal gevonden, wordt het op een na kleinste element verwisseld met het element in de 2e positie.

Dit proces gaat door totdat we het n-1e element van de array bereiken, waardoor het n-1e kleinste element op de n-1e positie komt te staan. Het laatste element valt automatisch op zijn plaats, in de n-1ste iteratie, waardoor de array wordt gesorteerd.

We vinden het grootste element in plaats van het kleinste element om de array in aflopende volgorde te sorteren.

Laten we een voorbeeld bekijken van een ongesorteerde array en deze in oplopende volgorde sorteren om het algoritme visueel te begrijpen.

2.1. Een voorbeeld

Beschouw de volgende ongesorteerde array:

int [] arr = {5, 4, 1, 6, 2}

Iteratie 1

Gezien de bovenstaande werking van het algoritme, beginnen we met het element op positie 1 - 5 - en scannen we door alle volgende elementen om het kleinste element te vinden - 1. We ruilen dan het kleinste element met het element op positie 1.

De gewijzigde reeks nu ziet eruit als:

{ 1 , 4 , 5 , 6 , 2 }

Totaal aantal gemaakte vergelijkingen: 4

Iteratie 2

In de tweede iteratie gaan we verder naar het 2e element - 4 - en scannen we door de volgende elementen om het op een na kleinste element te vinden - 2. We ruilen dan het tweede kleinste element met het element op de 2e positie.

De gewijzigde array ziet er nu als volgt uit:

{ 1 , 2 , 5 , 6 , 4 }

Totaal aantal gemaakte vergelijkingen: 3

Evenzo verdergaand, hebben we de volgende iteraties:

Iteratie 3

{ 1 , 2 , 4 , 6 , 5 }

Totaal gemaakte vergelijkingen: 2

Iteratie 4

{ 1 , 2 , 4 , 5 , 6 }

Totaal aantal gemaakte vergelijkingen: 1

3.Implementatie

Laten we Selectie sorteren implementeren met een paar voor lussen:

openbare statische ongeldige sortAscending (final int [] arr) {for (int i = 0; i <arr.length - 1; i ++) {int minElementIndex = i; voor (int j = i + 1; j arr [j]) {minElementIndex = j; }} if (minElementIndex! = i) {int temp = arr [i]; arr [i] = arr [minElementIndex]; arr [minElementIndex] = temp; }}}

Om het ongedaan te maken, zouden we natuurlijk iets vergelijkbaars kunnen doen:

public static void sortDescending (final int [] arr) {for (int i = 0; i <arr.length - 1; i ++) {int maxElementIndex = i; for (int j = i + 1; j <arr.length; j ++) {if (arr [maxElementIndex] <arr [j]) {maxElementIndex = j; }} if (maxElementIndex! = i) {int temp = arr [i]; arr [i] = arr [maxElementIndex]; arr [maxElementIndex] = temp; }}}

En met een beetje meer elleboogvet zouden we deze kunnen combineren met Comparators.

4. Prestatieoverzicht

4.1. Tijd

In het voorbeeld dat we eerder zagen, voor het selecteren van het kleinste element was in totaal (n-1) vergelijkingen gevolgd door het omwisselen naar de 1e positie. Evenzo het selecteren van het eerstvolgende kleinste vereiste element (n-2) vergelijkingen gevolgd door ruilen op de 2e positie, enzovoort.

Dus, beginnend bij index 0, presteren we n-1, n-2, n-3, n-4…. 1 vergelijkingen. Het laatste element valt automatisch op zijn plaats als gevolg van eerdere iteraties en swaps.

Wiskundig gezien is de som van de eerste n-1 natuurlijke cijfers zal ons vertellen hoeveel vergelijkingen we nodig hebben om een ​​array van grootte te sorteren n met behulp van Selectie sorteren.

De formule voor de som van n natuurlijke getallen is n (n + 1) / 2.

In ons geval hebben we de som van first nodig n-1 natuurlijke cijfers. Daarom vervangen we n met n-1 in de bovenstaande formule om te krijgen:

(n-1) (n-1 + 1) / 2 = (n-1) n / 2 = (n ^ 2-n) / 2

Net zo n ^ 2 groeit prominent als n groeit, beschouwen we de hogere macht van n als prestatiebenchmark, waardoor dit algoritme een tijd complexiteit van O (n ^ 2).

4.2. Ruimte

Wat betreft de complexiteit van de hulpruimte, heeft Selection Sort één extra variabele nodig om de waarde tijdelijk vast te houden voor verwisseling. Daarom Selection Sort's ruimte complexiteit is O (1).

5. Conclusie

Selection Sort is een heel eenvoudig sorteeralgoritme om te begrijpen en te implementeren. Helaas, zijn kwadratische tijdscomplexiteit maakt het een dure sorteertechniek. Omdat het algoritme door elk element moet scannen, de tijdcomplexiteit in het beste geval, het gemiddelde geval en in het slechtste geval is hetzelfde.

Andere sorteertechnieken zoals Insertion Sort en Shell Sort hebben ook kwadratische worst-case tijdcomplexiteit, maar ze presteren beter in de beste en gemiddelde gevallen.

Bekijk de volledige code voor Selectie Sorteren op GitHub.