streamalism.org

1. Uvod

U ovom uputstvu opisat ćemo algoritam sortiranja ljuske u Javi.

2. Pregled sortiranja školjke

2.1. Opis

Prvo opišimo algoritam sortiranja Shell kako bismo znali što pokušavamo implementirati.

Razvrstavanje ljuske temelji se na algoritmu za sortiranje Insertion i spada u skupinu vrlo učinkovitih algoritama. Općenito, algoritam razbija izvorni skup na manje podskupove, a zatim se svaki od njih sortira pomoću sortiranja umetanjem.

No, kako to čini podskupove nije jednostavno. Ne bira susjedne elemente za formiranje podskupa kao što bismo mogli očekivati. Umjesto toga, sortiranje ljuske koristi tzv interval ili jaz za stvaranje podskupa. Na primjer, ako imamo jaz Ja, to znači da će jedan podskup sadržavati elemente koji jesu Ja položaji razdvojeni.

Prvo, algoritam sortira elemente koji su međusobno udaljeni. Zatim, jaz postaje manji i uspoređuju se bliži elementi. Na taj se način neki elementi koji nisu u ispravnom položaju mogu pozicionirati brže nego da smo podskupove napravili od susjednih elemenata.

2.2. Primjer

Pogledajmo to u primjeru s prazninama 3 i 1 i nesortiranim popisom od 9 elemenata:

Ako slijedimo gornji opis, u prvoj iteraciji imat ćemo tri podskupa s 3 elementa (istaknuta istom bojom):

Nakon sortiranja svakog od podskupova u prvoj iteraciji, popis će izgledati ovako:

Možemo primijetiti da, iako još nemamo razvrstani popis, elementi su sada bliži željenim položajima.

Konačno, moramo napraviti još jednu sortiranje s priraštajem od jedne i to je zapravo osnovna sortacija umetanja. Broj operacija prebacivanja koje moramo izvršiti za sortiranje popisa sada je manji nego što bi to bio slučaj da nismo napravili prvu iteraciju:

2.3. Odabir sekvenci razmaka

Kao što smo spomenuli, sortiranje ljuske ima jedinstveni način odabira sljedova praznina. To je težak zadatak i trebali bismo biti oprezni da ne odaberemo premalo ili previše praznina. Više pojedinosti može se naći u popisu najčešće predloženih sekvenci praznina.

3. Provedba

Pogledajmo sada provedbu. Koristit ćemo Shell-ov izvorni slijed za intervalne korake:

N / 2, N / 4,…, 1 (kontinuirano dijeljenje s 2)

Sama provedba nije previše složena:

javna sortiranje praznina (int arrayToSort []) {int n = arrayToSort.length; for (int gap = n / 2; jaz> 0; jaz / = 2) {for (int i = jaz; i = jaz && arrayToSort [j - jaz]> ključ) {arrayToSort [j] = arrayToSort [j - jaz ]; j - = praznina; } arrayToSort [j] = ključ; }}}

Prvo smo stvorili niz praznina s petljom for, a zatim smo izvršili sortiranje umetanja za svaku veličinu praznine.

Sada možemo lako testirati našu metodu:

@Test javna praznina givenUnsortedArray_whenShellSort_thenSortedAsc () {int [] input = {41, 15, 82, 5, 65, 19, 32, 43, 8}; ShellSort.sort (input); int [] očekuje se = {5, 8, 15, 19, 32, 41, 43, 65, 82}; assertArrayEquals ("dva polja nisu jednaka", očekuje se, ulaz); }

4. Složenost

Općenito, algoritam sortiranja ljuske vrlo je učinkovit kod popisa srednje veličine. Složenost je teško odrediti, jer ona uvelike ovisi o slijedu praznina, ali vremenska složenost varira između NA) i O (N ^ 2).

Kompozicija prostora u najgorem slučaju je NA) s O (1) pomoćni prostor.

5. Zaključak

U ovom uputstvu opisali smo Shell sort i ilustrirali kako ga možemo implementirati u Javi.

Kao i obično, cijeli se kôd može naći na GitHubu.