streamalism.org

1. Úvod

V tejto príručke vysvetlíme, ako funguje algoritmus triedenia na mieste.

2. Algoritmy na mieste

Algoritmy na mieste sú tie, ktoré na transformáciu vstupných údajov nepotrebujú žiadnu pomocnú dátovú štruktúru. V zásade to znamená, že algoritmus nepoužíva na manipuláciu so vstupom ďalší priestor. Prakticky prepíše vstup s výstupom.

Avšak v skutočnosti môže algoritmus skutočne vyžadovať malý a nekonštantný ďalší priestor pre pomocné premenné. Zložitosť tohto priestoru je vo väčšine prípadov O (log n), aj keď niekedy je povolené niečo menej ako lineárne.

3. Pseudokód

Pozrime sa teraz na nejaký pseudokód a porovnajme algoritmus na mieste s algoritmom na mieste.

Budeme predpokladať, že chceme zvrátiť pole n čísla.

3.1. Algoritmus na mieste

Ak sa zamyslíme nad problémom, uvidíme, že ako výstup máme vstupné pole a obrátené pole. Nakoniec vlastne nepotrebujeme naše pôvodné pole, iba to obrátené.

Prečo by sme potom neprepísali vstup namiesto toho, aby sme jeho hodnoty presunuli do úplne nového poľa, pretože by to mohlo vyzerať ako najočividnejšia metóda? Urobiť to, budeme potrebovať iba jednu ďalšiu premennú na dočasné uloženie hodnôt, s ktorými momentálne pracujeme:

reversInPlace (pole A [n]) pre i od 0 do n / 2 teplota = A [i] A [i] = A [n - 1 - i] A [n - 1 - i] = teplota

Je potrebné spomenúť, že bez ohľadu na to, aké veľké je pole, extra priestor, ktorý potrebujeme, bude vždy O (1) v tomto prípade.

Obrázok ukazuje, že potrebujeme menej krokov ako v predchádzajúcom prípade:

3.2. Algoritmus na mieste

Na druhej strane to môžeme urobiť aj celkom jednoduchým a zrejmejším spôsobom. Môžeme vytvoriť nové pole rovnakej veľkosti, skopírovať hodnoty z pôvodného v príslušnom poradí a potom pôvodné pole odstrániť:

reverseOutOfPlace (pole A [n]) vytvoriť nové pole B [n] pre i od 0 do n - 1 B [i] = A [i] vymazať A návrat B

Aj keď to urobí to, čo sme chceli, nie je to dosť efektívne. Máme O (n) je potrebný ďalší priestorpretože máme dve polia na manipuláciu. Okrem toho je vytváranie a odstraňovanie nového poľa zvyčajne pomalá operácia.

Pozrime sa na ilustráciu procesu:

4. Implementácia Java

Pozrime sa teraz, ako môžeme implementovať v Jave to, čo sme sa naučili v predchádzajúcej časti.

Najskôr implementujeme miestny algoritmus:

public static int [] reverseInPlace (int A []) {int n = A.length; pre (int i = 0; i <n / 2; i ++) {int temp = A [i]; A [i] = A [n - l - i]; A [n - l - i] = teplota; } návrat A; }

Môžeme ľahko otestovať, že to funguje podľa očakávania:

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

Po druhé, poďme sa pozrieť na implementáciu algoritmu out-of-place:

public static int [] reverseOutOfPlace (int A []) {int n = A.length; int [] B = nový int [n]; pre (int i = 0; i <n; i ++) {B [n - i - 1] = A [i]; } návrat B; }

Test je dosť priamy:

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

5. Príklady

Existuje mnoho algoritmov triedenia, ktoré využívajú prístup na mieste. Niektoré z nich sú triedenie podľa vloženia, triedenie podľa bublín, triedenie podľa hromady, rýchle triedenie a triedenie podľa shellu. Môžete sa o nich dozvedieť viac a pozrieť si ich implementácie Java.

Musíme spomenúť aj druh hrebeňa a honduras. Všetky tieto majú priestorovú zložitosť O (log n).

Mohlo by byť tiež užitočné dozvedieť sa viac o teórii notácie Big-O a pozrieť sa na niektoré praktické príklady jazyka Java týkajúce sa zložitosti algoritmu.

6. Záver

V tomto článku sme popísali takzvané miestne algoritmy, objasnili ich fungovanie pomocou pseudokódu a niekoľko príkladov, vymenovali sme niekoľko algoritmov fungujúcich na tomto princípe a nakoniec sme implementovali základné príklady v prostredí Java.

Celý kód ako obvykle nájdete na GitHube.