streamalism.org

1. Introduktion

I denne vejledning vil vi lære Selection Sort, se implementeringen i Java og analysere dens ydeevne.

2. Algoritmeoversigt

Valg af sortering begynder med elementet i 1. position af et usorteret array og scanner gennem efterfølgende elementer til find det mindste element. Når det er fundet, byttes det mindste element ud med elementet i 1. position.

Algoritmen bevæger sig derefter videre til elementet i 2. position og scanner gennem efterfølgende elementer for at finde indekset for det 2. mindste element. Når det er fundet, byttes det næstmindste element med elementet i 2. position.

Denne proces fortsætter, indtil vi når n-1-elementet i arrayet, hvilket placerer n-1th-mindste element i n-1-position. Det sidste element falder automatisk på plads i n-1. Iteration og derved sorterer arrayet.

Vi finder det største element i stedet for det mindste element for at sortere arrayet i faldende rækkefølge.

Lad os se et eksempel på et usorteret array og sortere det i stigende rækkefølge for visuelt at forstå algoritmen.

2.1. Et eksempel

Overvej følgende usorterede array:

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

Iteration 1

I betragtning af ovenstående funktion af algoritmen starter vi med elementet i 1. position - 5 - og scanner gennem alle efterfølgende elementer for at finde det mindste element - 1. Vi bytter derefter det mindste element med elementet i 1. position.

Den ændrede matrixnow ser ud:

{ 1 , 4 , 5 , 6 , 2 }

Samlede sammenligninger: 4

Iteration 2

I den anden iteration går vi videre til det 2. element - 4 - og scanner gennem efterfølgende elementer for at finde det næstmindste element - 2. Vi bytter derefter det andet mindste element med elementet i 2. position.

Det modificerede array ser nu ud:

{ 1 , 2 , 5 , 6 , 4 }

Samlede sammenligninger: 3

Fortsat på samme måde har vi følgende gentagelser:

Iteration 3

{ 1 , 2 , 4 , 6 , 5 }

Samlede sammenligninger: 2

Iteration 4

{ 1 , 2 , 4 , 5 , 6 }

Samlede sammenligninger: 1

3.Implementering

Lad os implementere Selection Sort ved hjælp af et par til sløjfer:

offentlig statisk ugyldig sortAscending (final int [] arr) {for (int i = 0; i <arr.length - 1; i ++) {int minElementIndex = i; for (int j = i + 1; j arr [j]) {minElementIndex = j; }} hvis (minElementIndex! = i) {int temp = arr [i]; arr [i] = arr [minElementIndex]; arr [minElementIndex] = temp; }}}

Selvfølgelig for at vende det kunne vi gøre noget helt ens:

offentlig statisk ugyldig 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; }} hvis (maxElementIndex! = i) {int temp = arr [i]; arr [i] = arr [maxElementIndex]; arr [maxElementIndex] = temp; }}}

Og med lidt mere albuefedt kunne vi kombinere disse ved hjælp af Komparators.

4. Ydeevneoversigt

4.1. Tid

I eksemplet, som vi så tidligere, at vælge det mindste element krævede i alt (n-1) sammenligninger efterfulgt af at bytte den til 1. position. Tilsvarende valg af det næste mindste element, der kræves i alt (n-2) sammenligninger efterfulgt af bytte i 2. position og så videre.

Således starter vi fra indeks 0 n-1, n-2, n-3, n-4…. 1 sammenligninger. Det sidste element falder automatisk på plads på grund af tidligere iterationer og swaps.

Matematisk set summen af ​​det første n-1 naturlige tal vil fortælle os, hvor mange sammenligninger vi har brug for for at sortere en matrix af størrelse n ved hjælp af Selection Sort.

Formlen for summen af n naturlige tal er n (n + 1) / 2.

I vores tilfælde har vi brug for summen af ​​først n-1 naturlige tal. Derfor erstatter vi n med n-1 i ovenstående formel for at få:

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

Som n ^ 2 vokser fremtrædende som n vokser, betragter vi den højere magt af n som præstationsbenchmark, hvilket gør denne algoritme til en tidskompleksitet af O (n ^ 2).

4.2. Plads

Med hensyn til hjælpepladskompleksitet kræver Selection Sort en ekstra variabel for at holde værdien midlertidigt til swapping. Derfor er Selection Sort rumkompleksitet er O (1).

5. Konklusion

Selection Sort er en meget enkel sorteringsalgoritme at forstå og implementere. Desværre, dens kvadratiske tidskompleksitet gør det til en dyr sorteringsteknik. Da algoritmen også skal scanne gennem hvert element, det bedste tilfælde, gennemsnittet og tidskompleksiteten i værste tilfælde er den samme.

Andre sorteringsteknikker som Insertion Sort og Shell Sort har også kvadratisk worst-case tidskompleksitet, men de fungerer bedre i bedste og gennemsnitlige tilfælde.

Tjek den komplette kode for Selection Sort over på GitHub.