Indsættelse Sorter i Java

1. Oversigt

I denne vejledning skal vi diskutere Insertion Sort-algoritmen og se på dens Java-implementering.

Insertion Sort er en effektiv algoritme til bestilling af et lille antal varer. Denne metode er baseret på den måde, kortspillere sorterer en hånd på at spille kort.

Vi starter med en tom venstre hånd og kortene lagt på bordet. Vi fjerner derefter et kort ad gangen fra bordet og indsætter det i den rigtige position i venstre hånd. For at finde den rigtige position for et nyt kort sammenligner vi det med det allerede sorterede sæt kort i hånden, fra højre mod venstre.

Lad os starte med at forstå algoritmetrinene i pseudokodeform.

2. Pseudokode

Vi præsenterer vores pseudokode til indsættelsessortering som en procedure kaldet INDFØRELSESORTERING, tager som parameter en matrix A [1 .. n] af n varer, der skal sorteres. Algoritmen sorterer inputmatrixen på plads (ved at omarrangere elementerne i array A).

Når proceduren er afsluttet, indeholder inputmatrix A en permutation af indgangssekvensen, men i sorteret rækkefølge:

INSERTION-SORT (A) for i = 2 til A. længdetast = A [i] j = i - 1 mens j> 0 og A [j]> tast A [j + 1] = A [j] j = j - 1 A [j + 1] = tast

Lad os kort gennemgå algoritmen ovenfor.

Indekset jeg angiver placeringen af ​​det aktuelle element i det array, der skal behandles.

Vi starter fra det andet element, da en matrix med et element pr. Definition anses for at være sorteret. Varen ved indeks jeg kaldes en nøgle. Når du har en nøgle, anden del af algoritmen beskæftiger sig med at finde dens korrekte indeks. Hvis den nøgle er mindre end elementets værdi ved indeks j, så bevæger nøglen sig en position til venstre. Processen fortsætter indtil det tilfælde, hvor vi når et element, der er mindre end nøglen.

Det er vigtigt at bemærke, at inden iteration med henblik på at finde den korrekte position af nøgle ved indeks jeg, arrayet A [1 .. j - 1] er allerede sorteret.

3. Imperativ implementering

I det tvingende tilfælde skal vi skrive en funktion kaldet insertionSortImperative, idet der tages som parameter en række heltal. Funktionen starter iterering over arrayet fra det andet element.

På et hvilket som helst tidspunkt under iteration, vi kunne tænke på denne matrix som logisk opdelt i to dele; den venstre side er den sorterede ene og den højre side, der indeholder de varer, der endnu ikke er sorteret.

En vigtig note her er, at efter at have fundet den rigtige position, hvor vi indsætter den nye vare, vi skifter (og bytter ikke) elementerne til højre at frigøre plads til det.

offentlig statisk tomrumsindsættelseSortImperative (int [] input) {for (int i = 1; i = 0 && input [j]> tast) {input [j + 1] = input [j]; j = j - 1; } input [j + 1] = tast; }}

Lad os derefter oprette en test for metoden ovenfor:

@Test offentlig ugyldighed givenUnsortedArray_whenInsertionSortImperative_thenSortedAsc () {int [] input = {6, 2, 3, 4, 5, 1}; InsertionSort.insertionSortImperative (input); int [] forventet = {1, 2, 3, 4, 5, 6}; assertArrayEquals ("de to arrays er ikke ens", forventet, input); }

Testen ovenfor viser, at algoritmen sorterer korrekt i stigende rækkefølge input-arrayet .

4. Rekursiv implementering

Funktionen til det rekursive tilfælde kaldes indsættelseSortRecursive og accepterer som input en matrix af heltal (det samme som for det tvingende tilfælde).

Forskellen her fra det tvingende tilfælde (på trods af at det er rekursivt) er, at det kalder en overbelastet funktion med et andet argument, der svarer til antallet af poster, der skal sorteres.

Da vi vil sortere det komplette array, sender vi et antal poster svarende til længden:

offentlig statisk ugyldig indsættelseSortRecursive (int [] input) {insertionSortRecursive (input, input.length); }

Den rekursive sag er lidt mere udfordrende. Basissagen opstår, når vi forsøger at sortere en matrix med et element. I dette tilfælde gør vi intet.

Alle de efterfølgende rekursive opkald sorterer en foruddefineret del af input-arrayet - startende fra det andet element, indtil vi når slutningen af ​​arrayet:

privat statisk tomrumsindsættelseSortRecursive (int [] input, int i) {if (i <= 1) {return; } insertionSortRecursive (input, i - 1); int-nøgle = input [i - 1]; int j = i - 2; mens (j> = 0 && input [j]> -tast) {input [j + 1] = input [j]; j = j - 1; } input [j + 1] = tast; }

Og sådan ser opkaldstakken ud for et inputarray på 6 emner:

insertionSortRecursive (input, 6) insertionSortRecursive (input, 5) og indsæt det 6. element i det sorterede array insertionSortRecursive (input, 4) og indsæt det 5. element i det sorterede array indsættelseSortRecursive (input, 3) og indsæt det 4. element i det sorterede array insertionSortRecursive (input, 2) og indsæt det 3. element i det sorterede array insertionSortRecursive (input, 1) og indsæt det 2. element i det sorterede array

Lad os også se testen for det:

@Test offentlig ugyldighed givenUnsortedArray_whenInsertionSortRecursively_thenSortedAsc () {int [] input = {6, 4, 5, 2, 3, 1}; InsertionSort.insertionSortRecursive (input); int [] forventet = {1, 2, 3, 4, 5, 6}; assertArrayEquals ("de to arrays er ikke ens", forventet, input); }

Ovenstående test viser, at algoritmen sorterer korrekt i stigende rækkefølge input-arrayet .

5. Kompleksitet i tid og rum

Den tid, det tager af INDFØRELSESORTERING procedure at køre er O (n ^ 2). For hvert nye element gentager vi fra højre til venstre over den allerede sorterede del af arrayet for at finde den korrekte position. Derefter indsætter vi det ved at flytte elementerne en position til højre.

Algoritmen sorteres på plads, så dens rumkompleksitet er O (1) for den tvingende gennemførelse og På) til den rekursive implementering.

6. Konklusion

I denne vejledning så vi, hvordan man implementerer indsættelsessortering.

Denne algoritme er nyttig til at sortere et lille antal ting. Det bliver ineffektivt ved sortering af indgangssekvenser med mere end 100 elementer.

Husk, at det til trods for dets kvadratiske kompleksitet sorteres på plads uden behov for hjælpeplads, som det er tilfældet med flet sortering.

Hele koden kunne findes på GitHub.