streamalism.org

1. Oversikt

I denne opplæringen skal vi diskutere Insertion Sort-algoritmen og se på Java-implementeringen.

Insertion Sort er en effektiv algoritme for å bestille et lite antall varer. Denne metoden er basert på måten kortspillere sorterer en hånd med spillkort.

Vi starter med en tom venstre hånd og kortene lagt på bordet. Vi fjerner deretter ett kort om gangen fra bordet og setter det i riktig posisjon i venstre hånd. For å finne riktig posisjon for et nytt kort, sammenligner vi det med det allerede sorterte settet med kort i hånden, fra høyre til venstre.

La oss starte med å forstå algoritmetrinnene i pseudokodeform.

2. Pseudokode

Vi skal presentere pseudokoden vår for innsetting som en prosedyre kalt INNFØRING-SORTERING, tar som parameter en matrise A [1 .. n] av n gjenstander som skal sorteres. Algoritmen sorterer inndata-matrisen på plass (ved å omorganisere elementene i matrisen A).

Etter at prosedyren er ferdig, inneholder inngangsmatrisen A en permutasjon av inngangssekvensen, men i sortert rekkefølge:

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

La oss kort gå over algoritmen ovenfor.

Indeksen Jeg angir posisjonen til gjeldende element i matrisen som skal behandles.

Vi begynner fra det andre elementet som per definisjon en matrise med ett element anses å være sortert. Elementet ved indeks Jeg kalles en nøkkel. Når du har den nøkkel, den andre delen av algoritmen handler om å finne riktig indeks. Hvis den nøkkel er mindre enn verdien på varen ved indeks j, deretter flytter nøkkelen en posisjon mot venstre. Prosessen fortsetter til tilfellet når vi når et element som er mindre enn nøkkelen.

Det er viktig å merke seg at før du starter iterasjonen for å finne den riktige posisjonen til nøkkel ved indeks Jeg, matrisen A [1 .. j - 1] er allerede sortert.

3. Imperativ implementering

For det tvingende tilfellet skal vi skrive en funksjon som heter innsettingSortImperative, tar som en parameter en rekke heltall. Funksjonen begynner å itere over matrisen fra det andre elementet.

Til enhver tid under iterasjonen, vi kunne tenke på denne matrisen som å være logisk delt i to deler; venstre side er den sorterte og høyre side som inneholder elementene som ennå ikke er sortert.

En viktig merknad her er at etter å ha funnet riktig posisjon der vi setter inn det nye elementet, vi skifter (og bytter ikke) elementene til høyre for å frigjøre plass til det.

offentlig statisk tominnsettingSortImperative (int [] input) {for (int i = 1; i = 0 && input [j]> key) {input [j + 1] = input [j]; j = j - 1; } inngang [j + 1] = tast; }}

Deretter la oss lage en test for metoden ovenfor:

@Test offentlig ugyldighet gittUnsortedArray_whenInsertionSortImperative_thenSortedAsc () {int [] input = {6, 2, 3, 4, 5, 1}; InsertionSort.insertionSortImperative (input); int [] forventet = {1, 2, 3, 4, 5, 6}; assertArrayEquals ("de to matriser er ikke like", forventet, input); }

Testen ovenfor viser at algoritmen sorterer riktig i stigende rekkefølge inngangsruten .

4. Rekursiv implementering

Funksjonen for det rekursive tilfellet kalles innsettingSortRekursiv og godtar som inngang en rekke heltall (samme som for imperativt tilfelle).

Forskjellen her fra den tvingende saken (til tross for at den er rekursiv) er at den kaller en overbelastet funksjon med et annet argument som tilsvarer antall elementer som skal sorteres.

Når vi vil sortere hele matrisen, sender vi et antall elementer som er like lange:

public static void insertionSortRecursive (int [] input) {insertionSortRecursive (input, input.length); }

Den rekursive saken er litt mer utfordrende. Basissaken oppstår når vi prøver å sortere en matrise med ett element. I dette tilfellet gjør vi ingenting.

Alle de etterfølgende rekursive anropene sorterer en forhåndsdefinert del av inngangsruten - fra det andre elementet til vi når slutten av matrisen:

privat statisk tominnsettingSortRecursive (int [] input, int i) {if (i <= 1) {return; } innsettingSortRecursive (input, i - 1); int-tast = inngang [i - 1]; int j = i - 2; mens (j> = 0 && input [j]> key) {input [j + 1] = input [j]; j = j - 1; } inngang [j + 1] = tast; }

Og dette er hvordan samtalestakken ser ut for en inngangssamling på 6 elementer:

insertionSortRecursive (input, 6) insertionSortRecursive (input, 5) og sett inn det 6. elementet i den sorterte matrixinnsatsenSortRecursive (input, 4) og sett inn det 5. elementet i det sorterte arrayet array insertionSortRecursive (input, 2) og sett inn det tredje elementet i det sorterte arrayet insertionSortRecursive (input, 1) og sett det andre elementet i den sorterte arrayet

La oss også se testen for det:

@Test offentlig ugyldig 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 matriser er ikke like", forventet, input); }

Testen ovenfor viser at algoritmen sorterer riktig i stigende rekkefølge inngangsruten .

5. Tid og romkompleksitet

Tiden det tok av INNFØRING-SORTERING prosedyre å kjøre er O (n ^ 2). For hvert nye element, gjentar vi fra høyre til venstre over den allerede sorterte delen av matrisen for å finne riktig posisjon. Deretter setter vi det inn ved å flytte elementene en posisjon til høyre.

Algoritmen sorterer på plass slik at den er romkompleksitet er O (1) for den tvingende gjennomføringen og På) for den rekursive implementeringen.

6. Konklusjon

I denne opplæringen så vi hvordan vi implementerer innsettingssortering.

Denne algoritmen er nyttig for å sortere et lite antall elementer. Det blir ineffektivt når du sorterer inngangssekvenser med mer enn 100 elementer.

Husk at til tross for den kvadratiske kompleksiteten, sorterer den på plass uten behov for ekstra plass, slik det er tilfelle for slå sammen.

Hele koden kan bli funnet på GitHub.