streamalism.org

1. Introduksjon

I denne opplæringen vil vi lære Selection Sort, se implementeringen i Java, og analysere ytelsen.

2. Algoritmeoversikt

Utvalg Sorter begynner med elementet i 1. posisjon av en usortert matrise og skanner gjennom påfølgende elementer til finn det minste elementet. Når det er funnet, byttes det minste elementet ut med elementet i 1. posisjon.

Algoritmen beveger seg deretter til elementet i 2. posisjon og skanner gjennom påfølgende elementer for å finne indeksen til det 2. minste elementet. Når det er funnet, byttes det nest minste elementet ut med elementet i 2. posisjon.

Denne prosessen fortsetter til vi når n-1-elementet i matrisen, som setter n-1. Minste element i n-1-posisjon. Det siste elementet faller automatisk på plass, i n-1. Iterasjon, og sorterer derved matrisen.

Vi finner det største elementet i stedet for det minste elementet for å sortere matrisen i synkende rekkefølge.

La oss se et eksempel på en usortert matrise og sortere den i stigende rekkefølge for å forstå algoritmen visuelt.

2.1. Et eksempel

Vurder følgende usorterte matrise:

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

Iterasjon 1

Tatt i betraktning den ovennevnte funksjonen til algoritmen, begynner vi med elementet i 1. posisjon - 5 - og skanner gjennom alle påfølgende elementer for å finne det minste elementet - 1. Vi bytter deretter det minste elementet med elementet i 1. posisjon.

De modifiserte array nows ser ut som:

{ 1 , 4 , 5 , 6 , 2 }

Totale sammenligninger: 4

Iterasjon 2

I den andre iterasjonen går vi videre til det andre elementet - 4 - og skanner gjennom påfølgende elementer for å finne det nest minste elementet - 2. Vi bytter deretter det nest minste elementet med elementet i 2. posisjon.

Den modifiserte matrisen ser nå ut som:

{ 1 , 2 , 5 , 6 , 4 }

Totale sammenligninger: 3

Fortsetter vi på samme måte, har vi følgende iterasjoner:

Iterasjon 3

{ 1 , 2 , 4 , 6 , 5 }

Totale sammenligninger: 2

Iterasjon 4

{ 1 , 2 , 4 , 5 , 6 }

Totale sammenligninger gjort: 1

3.Gjennomføring

La oss implementere Selection Sort ved hjelp av et par til sløyfer:

offentlig statisk tomrom 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 å snu det, kunne vi gjøre noe ganske likt:

offentlig statisk tomrom 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 litt mer albuefett, kunne vi kombinere disse ved hjelp av Komparators.

4. Ytelsesoversikt

4.1. Tid

I eksemplet vi så tidligere, å velge det minste elementet krevde totalt (n-1) sammenligninger etterfulgt av å bytte den til 1. posisjon. På samme måte, velge det nest minste elementet som kreves totalt (n-2) sammenligninger fulgt av bytte i 2. posisjon, og så videre.

Således starter vi fra indeks 0 n-1, n-2, n-3, n-4…. 1 sammenligninger. Det siste elementet faller automatisk på plass på grunn av tidligere iterasjoner og bytter.

Matematisk, den summen av det første n-1 naturlige tall vil fortelle oss hvor mange sammenligninger vi trenger for å sortere en rekke størrelser n ved hjelp av Selection Sort.

Formelen for summen av n naturlige tall er n (n + 1) / 2.

I vårt tilfelle trenger vi summen av først n-1 naturlige tall. Derfor erstatter vi n med n-1 i formelen ovenfor for å få:

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

Som n ^ 2 vokser fremtredende som n vokser, anser vi den høyere kraften i n som ytelsesverdien, noe som gjør at denne algoritmen har en tidskompleksitet av O (n ^ 2).

4.2. Rom

Når det gjelder ekstra romkompleksitet, krever Selection Sort en ekstra variabel for å holde verdien midlertidig for bytte. Derfor er Selection Sort romkompleksitet er O (1).

5. Konklusjon

Selection Sort er en veldig enkel sorteringsalgoritme å forstå og implementere. Dessverre, den kvadratiske tidskompleksiteten gjør det til en dyr sorteringsteknikk. Siden algoritmen må skanne gjennom hvert element, best case, gjennomsnittlig case og worst-case tidskompleksitet er den samme.

Andre sorteringsteknikker som Insertion Sort og Shell Sort har også kvadratisk tidskompleksitet i verste fall, men de fungerer bedre i beste og gjennomsnittlige tilfeller.

Sjekk ut den fullstendige koden for Selection Sort over på GitHub.