Valg Sorter i Java
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.