streamalism.org

1. Prehľad

V tomto výučbe budeme diskutovať algoritmus Insertion Sort a pozrite sa na jeho implementáciu Java.

Insertion Sort je efektívny algoritmus na objednávanie malého počtu položiek. Táto metóda je založená na spôsobe triedenia kariet hráčmi.

Začíname s prázdnou ľavou rukou a kartami položenými na stole. Potom vyberáme po jednej karte zo stola a vložíme ju do správnej polohy v ľavej ruke. Aby sme našli novú pozíciu pre novú kartu, porovnáme ju s už zoradenou sadou kariet v ruke, sprava doľava.

Začnime pochopením krokov algoritmu vo forme pseudokódu.

2. Pseudokód

Predstavíme náš pseudokód na triedenie vloženia ako procedúru s názvom VLOŽENIE-Triedenie, berúc ako parameter pole A [1 .. n] z n položiek na triedenie. Algoritmus triedi vstupné pole na mieste (preskupením položiek v poli A).

Po dokončení procedúry obsahuje vstupné pole A permutáciu vstupnej sekvencie, ale v zoradenom poradí:

INSERTION-SORT (A) for i = 2 to A.lenght key = A [i] j = i - 1 while j> 0 and A [j]> key A [j + 1] = A [j] j = j - 1 A [j + 1] = kľúč

Poďme si v skratke prejsť na vyššie uvedený algoritmus.

Index i označuje pozíciu aktuálnej položky v poli na spracovanie.

Začíname od druhej položky, pretože podľa definície sa pole s jednou položkou považuje za triedené. Položka v indexe i sa nazýva a kľúč. Raz majú kľúč, druhá časť algoritmu sa zaoberá hľadaním jeho správneho indexu. Ak kľúč je menšia ako hodnota položky v indexe j, potom sa kláves presunie o jednu pozíciu doľava. Proces pokračuje až do prípadu, keď dosiahneme prvok menší ako kľúč.

Je dôležité si uvedomiť, že pred začatím iterácie na nájdenie správnej polohy súboru kľúč pri indexe i, pole A [1 .. j - 1] už je zoradené.

3. Imperatívna implementácia

Pre imperatívny prípad napíšeme funkciu s názvom insertionSortImperative, berúc ako parameter pole celých čísel. Funkcia začne iterovať nad poľom z druhej položky.

Kedykoľvek počas iterácie mohli by sme si myslieť, že toto pole je logicky rozdelené na dve časti; ľavá strana je zoradená jedna a pravá strana obsahujúca položky ešte netriedené.

Dôležitá poznámka je, že po nájdení správnej polohy, do ktorej vložíme novú položku, položky posúvame (a nemeníme) doprava uvoľniť pre to priestor.

public static void insertionSortImperative (int [] vstup) {for (int i = 1; i = 0 && vstup [j]> kľúč) {vstup [j + 1] = vstup [j]; j = j - 1; } vstup [j + 1] = kľúč; }}

Ďalej vytvoríme test pre vyššie uvedenú metódu:

@Test public void givenUnsortedArray_whenInsertionSortImperative_thenSortedAsc () {int [] vstup = {6, 2, 3, 4, 5, 1}; InsertionSort.insertionSortImperative (vstup); int [] očakávaný = {1, 2, 3, 4, 5, 6}; assertArrayEquals ("dve polia nie sú rovnaké", očakáva sa, vstup); }

Vyššie uvedený test dokazuje, že algoritmus triedi vstupné pole správne vo vzostupnom poradí .

4. Rekurzívna implementácia

Volá sa funkcia pre rekurzívny prípad insertionSortRrekurzívny a prijíma ako vstup pole celých čísel (rovnaké ako v prípade imperatívu).

Rozdiel od imperatívneho prípadu (napriek skutočnosti, že je to rekurzívny prípad) je v tom, že je zavolá preťaženú funkciu s druhým argumentom, ktorý sa rovná počtu položiek na triedenie.

Keď chceme zoradiť celé pole, odovzdáme množstvo položiek, ktoré sa rovnajú jeho dĺžke:

public static void insertionSortRecursive (int [] vstup) {insertionSortRecursive (vstup, vstup.lenka); }

Rekurzívny prípad je o niečo náročnejší. Základný prípad nastane, keď sa pokúsime zoradiť pole s jednou položkou. V takom prípade nerobíme nič.

Všetky nasledujúce rekurzívne volania triedia preddefinovanú časť vstupného poľa - od druhej položky až po koniec poľa:

private static void insertionSortRecursive (int [] vstup, int i) {if (i <= 1) {návrat; } insertionSortRecursive (vstup, i - 1); kľúč int = vstup [i - 1]; int j = i - 2; while (j> = 0 && vstup [j]> kľúč) {input [j + 1] = vstup [j]; j = j - 1; } vstup [j + 1] = kľúč; }

A takto vyzerá zásobník hovorov pre vstupné pole so 6 položkami:

insertionSortRecursive (vstup, 6) insertionSortRecursive (vstup, 5) a vložíme 6. položku do zoradeného poľa inserttionSortRecursive (vstup, 4) a vložíme 5. položku do zoradeného poľa insertionSortRecursive (vstup, 3) a vložíme 4. položku do zoradeného poľa pole insertionSortRecursive (vstup, 2) a vložte 3. položku do zoradeného poľa insertionSortRecursive (vstup, 1) a vložte 2. položku do zoradeného poľa

Pozrime sa tiež na test:

@Test public void givenUnsortedArray_whenInsertionSortRecursively_thenSortedAsc () {int [] vstup = {6, 4, 5, 2, 3, 1}; InsertionSort.insertionSortRecursive (vstup); int [] očakávané = {1, 2, 3, 4, 5, 6}; assertArrayEquals ("dva polia nie sú rovnaké", očakáva sa, vstup); }

Vyššie uvedený test dokazuje, že algoritmus triedi vstupné pole správne vo vzostupnom poradí .

5. Časová a priestorová zložitosť

Čas, ktorý VLOŽKA-Triedenie postup na spustenie je O (n ^ 2). Pre každú novú položku iterujeme sprava doľava cez už zoradenú časť poľa, aby sme našli jeho správnu pozíciu. Potom ju vložíme posunutím položiek o jednu pozíciu doprava.

Algoritmus je usporiadaný na svojom mieste zložitosť priestoru je O (1) za nevyhnutnú implementáciu a O (n) pre rekurzívnu implementáciu.

6. Záver

V tomto tutoriáli sme videli, ako implementovať triedenie vloženia.

Tento algoritmus je užitočný na triedenie malého počtu položiek. Stáva sa neefektívnym pri triedení vstupných sekvencií, ktoré majú viac ako 100 položiek.

Majte na pamäti, že aj napriek svojej kvadratickej zložitosti sa zoraďuje na mieste bez potreby pomocného priestoru, ako je to v prípade zlúčiť druh.

Celý kód nájdete na GitHub.