streamalism.org

1. Overzicht

In deze tutorial gaan we bespreken het Insertion Sort-algoritme en bekijk de Java-implementatie ervan.

Insertion Sort is een efficiënt algoritme voor het bestellen van een klein aantal items. Deze methode is gebaseerd op de manier waarop kaartspelers een hand met speelkaarten sorteren.

We beginnen met een lege linkerhand en de kaarten worden op tafel gelegd. We halen dan één kaart tegelijk van de tafel en steken deze in de juiste positie in de linkerhand. Om de juiste positie voor een nieuwe kaart te vinden, vergelijken we deze met de reeds gesorteerde set kaarten in de hand, van rechts naar links.

Laten we beginnen met het begrijpen van de algoritmestappen in pseudocodevorm.

2. Pseudocode

We gaan onze pseudocode voor invoegsortering presenteren als een procedure genaamd INVOEGSORTERING, met als parameter een array A [1 .. n] van n items die moeten worden gesorteerd. Het algoritme sorteert de invoerarray op zijn plaats (door de items in array A te herschikken).

Nadat de procedure is voltooid, bevat de invoerarray A een permutatie van de invoerreeks, maar in gesorteerde volgorde:

INSERTION-SORT (A) voor i = 2 tot A.length key = A [i] j = i - 1 terwijl j> 0 en A [j]> key A [j + 1] = A [j] j = j - 1 A [j + 1] = sleutel

Laten we het bovenstaande algoritme kort bespreken.

De index ik geeft de positie van het huidige item in de te verwerken array aan.

We beginnen bij het tweede item, aangezien een array met één item per definitie als gesorteerd wordt beschouwd. Het item bij index ik heet een sleutel. Zodra u de sleutel, het tweede deel van het algoritme gaat over het vinden van de juiste index. Als het sleutel is kleiner dan de waarde van het item bij index j, dan schuift de sleutel een positie naar links. Het proces gaat door totdat we een element bereiken dat kleiner is dan de sleutel.

Het is belangrijk op te merken dat voordat u de iteratie start om de juiste positie van het sleutel bij index ik, de array A [1 .. j - 1] is al gesorteerd.

3. Imperatieve implementatie

Voor het imperatieve geval gaan we een functie schrijven met de naam insertionSortImperative, met als parameter een reeks gehele getallen. De functie begint met itereren over de array vanaf het tweede item.

Op elk moment tijdens de iteratie, we zouden deze array kunnen beschouwen als logisch verdeeld in twee delen; de linkerkant is de gesorteerde en de rechterkant bevat de items die nog niet zijn gesorteerd.

Een belangrijke opmerking hierbij is dat na het vinden van de juiste positie waarop we het nieuwe item invoegen, we schuiven (en niet ruilen) de items naar rechts om er ruimte voor vrij te maken.

public static void insertionSortImperative (int [] input) {for (int i = 1; i = 0 && input [j]> key) {input [j + 1] = input [j]; j = j - 1; } input [j + 1] = sleutel; }}

Laten we vervolgens een test maken voor de bovenstaande methode:

@Test openbare leegte gegevenUnsortedArray_whenInsertionSortImperative_thenSortedAsc () {int [] input = {6, 2, 3, 4, 5, 1}; InsertionSort.insertionSortImperative (invoer); int [] verwacht = {1, 2, 3, 4, 5, 6}; assertArrayEquals ("de twee arrays zijn niet gelijk", verwacht, invoer); }

De bovenstaande test bewijst dat het algoritme de invoerarray correct sorteert in oplopende volgorde .

4. Recursieve implementatie

De functie voor het recursieve hoofdlettergebruik wordt aangeroepen insertionSortRecursief en accepteert als invoer een array van gehele getallen (hetzelfde als voor het imperatieve geval).

Het verschil hier met het imperatieve geval (ondanks het feit dat het recursief is) is dat het roept een overbelaste functie aan met een tweede argument dat gelijk is aan het aantal items dat moet worden gesorteerd.

Omdat we de volledige array willen sorteren, geven we een aantal items door die gelijk zijn aan de lengte:

openbare statische ongeldige insertionSortRecursive (int [] input) {insertionSortRecursive (input, input.length); }

Het recursieve geval is een beetje uitdagender. Het basisscenario treedt op wanneer we proberen een array met één item te sorteren. In dit geval doen we niets.

Alle volgende recursieve aanroepen sorteren een vooraf gedefinieerd deel van de invoerarray - beginnend bij het tweede item tot we het einde van de array bereiken:

private static void insertionSortRecursive (int [] input, int i) {if (i <= 1) {return; } insertionSortRecursive (input, i - 1); int key = input [i - 1]; int j = ik - 2; while (j> = 0 && input [j]> key) {input [j + 1] = input [j]; j = j - 1; } input [j + 1] = sleutel; }

En zo ziet de call-stack eruit voor een invoerarray van 6 items:

insertionSortRecursive (input, 6) insertionSortRecursive (input, 5) en plaats het 6e item in de gesorteerde array insertionSortRecursive (input, 4) en plaats het 5e item in de gesorteerde array insertionSortRecursive (input, 3) en voeg het 4e item in de gesorteerde array in. array insertionSortRecursive (input, 2) en plaats het 3e item in de gesorteerde array insertionSortRecursive (input, 1) en voeg het 2e item in de gesorteerde array in

Laten we ook de test ervoor bekijken:

@Test openbare leegte gegevenUnsortedArray_whenInsertionSortRecursively_thenSortedAsc () {int [] input = {6, 4, 5, 2, 3, 1}; InsertionSort.insertionSortRecursive (invoer); int [] verwacht = {1, 2, 3, 4, 5, 6}; assertArrayEquals ("de twee arrays zijn niet gelijk", verwacht, invoer); }

De bovenstaande test bewijst dat het algoritme de invoerarray correct sorteert in oplopende volgorde .

5. Complexiteit van tijd en ruimte

De tijd die de INVOEG-SORTEREN uit te voeren procedure is O (n ^ 2). Voor elk nieuw item itereren we van rechts naar links over het reeds gesorteerde gedeelte van de array om de juiste positie te vinden. Vervolgens voegen we het in door de items een positie naar rechts te verschuiven.

Het algoritme sorteert op zijn plaats zodat het ruimte complexiteit is O (1) voor de dwingende implementatie en Aan) voor de recursieve implementatie.

6. Conclusie

In deze zelfstudie hebben we gezien hoe invoegsortering kan worden geïmplementeerd.

Dit algoritme is handig voor het sorteren van een klein aantal items. Het wordt inefficiënt bij het sorteren van invoersequenties met meer dan 100 items.

Houd er rekening mee dat het ondanks zijn kwadratische complexiteit op zijn plaats kan worden gesorteerd zonder dat er extra ruimte nodig is, zoals het geval is bij samenvoegen sorteren.

De volledige code kan worden gevonden op GitHub.