streamalism.org

1. Úvod

V tomto tutoriále popíšeme algoritmus triedenia Shell v Jave.

2. Prehľad triedenia Shell

2.1. Popis

Poďme si najskôr popísať algoritmus triedenia Shell, aby sme vedeli, čo sa snažíme implementovať.

Shell sort je založený na algoritme triedenia Insertion a patrí do skupiny veľmi efektívnych algoritmov. Všeobecne, algoritmus rozbije pôvodnú množinu na menšie podmnožiny a potom je každá z nich roztriedená pomocou triedenia vloženia.

Ako však vytvára podmnožiny, nie je jednoduché. Nevyberá si susedné prvky na vytvorenie podmnožiny, ako by sme čakali. Skôr druh škrupiny používa tzv interval alebo medzera na vytvorenie podmnožiny. Napríklad, ak máme medzeru Ja, To znamená, že jedna podmnožina bude obsahovať prvky, ktoré sú Ja pozícií od seba.

Algoritmus najskôr triedi prvky, ktoré sú od seba ďaleko. Potom sa medzera zmenší a porovnajú sa bližšie prvky. Týmto spôsobom je možné umiestniť niektoré prvky, ktoré nie sú v správnej polohe, rýchlejšie, ako keby sme podmnožiny vytvorili zo susedných prvkov.

2.2. Príklad

Pozrime sa na príklade s medzerami 3 a 1 a netriedeným zoznamom 9 prvkov:

Ak sa budeme riadiť vyššie uvedeným popisom, v prvej iterácii budeme mať tri podmnožiny s 3 prvkami (zvýraznené rovnakou farbou):

Po zoradení každej z podmnožín v prvej iterácii by zoznam vyzeral takto:

Môžeme poznamenať, že hoci zatiaľ nemáme zoradený zoznam, prvky sú teraz bližšie k požadovaným pozíciám.

Nakoniec musíme urobiť ešte jeden druh s prírastkom jedného a je to vlastne základné triedenie vloženia. Počet operácií radenia, ktoré musíme vykonať na zoradenie zoznamu, je teraz menší, ako by to bolo v prípade, keby sme neurobili prvú iteráciu:

2.3. Výber sekvencií medzier

Ako sme už spomenuli, triedenie škrupín má jedinečný spôsob výberu sekvencií medzier. Toto je náročná úloha a mali by sme byť opatrní, aby sme nevybrali príliš málo alebo príliš veľa medzier. Viac podrobností nájdete v zozname navrhovaných sekvencií medzier.

3. Implementácia

Poďme sa teraz pozrieť na implementáciu. Pre intervalové prírastky použijeme pôvodnú postupnosť Shell:

N / 2, N / 4,…, 1 (nepretržite deliteľné 2)

Samotná implementácia nie je príliš zložitá:

public void sort (int arrayToSort []) {int n = arrayToSort.length; for (int gap = n / 2; gap> 0; gap / = 2) {for (int i = gap; i = gap && arrayToSort [j - gap]> key) {arrayToSort [j] = arrayToSort [j - gap ]; j - = medzera; } arrayToSort [j] = kľúč; }}}

Najprv sme vytvorili slučku medzery pomocou slučky for a potom sme vykonali triedenie vloženia pre každú veľkosť medzery.

Teraz môžeme našu metódu ľahko otestovať:

@Test public void givenUnsortedArray_whenShellSort_thenSortedAsc () {int [] vstup = {41, 15, 82, 5, 65, 19, 32, 43, 8}; ShellSort.sort (vstup); int [] očakávané = {5, 8, 15, 19, 32, 41, 43, 65, 82}; assertArrayEquals ("dva polia nie sú rovnaké", očakáva sa, vstup); }

4. Zložitosť

Spravidla algoritmus triedenia Shell je veľmi efektívny pri stredne veľkých zoznamoch. Zložitosť je ťažké určiť, pretože to veľa závisí od postupnosti medzier, ale časová zložitosť sa medzi nimi líši O (N) a O (N ^ 2).

Najhoršia zložitosť priestoru je O (N) s O (1) pomocný priestor.

5. Záver

V tomto tutoriáli sme opísali triedenie Shell a názorne sme ilustrovali, ako ho môžeme implementovať v Jave.

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