Shell Sort Java-ban

1. Bemutatkozás

Ebben az oktatóanyagban leírjuk a Shell rendezési algoritmust a Java-ban.

2. A Shell rendezés áttekintése

2.1. Leírás

Először írjuk le a Shell rendezési algoritmust, hogy tudjuk, mit próbálunk megvalósítani.

A héjfajta rendezése az Insertion rendezési algoritmuson alapul, és a nagyon hatékony algoritmusok csoportjába tartozik. Általánosságban, az algoritmus egy eredeti halmazt kisebb részhalmazokra bont, majd mindegyiket az Insertion sort segítségével rendezi.

De az, hogy ez hogyan készíti el az alcsoportokat, nem egyértelmű. Nem a szomszédos elemeket választja ki részhalmaz kialakításához, mint amire számíthatunk. A shell sort inkább az ún intervallum vagy rés részhalmaz létrehozásához. Például, ha megvan a rés én, ez azt jelenti, hogy egy részhalmaz tartalmazza azokat az elemeket, amelyek vannak én pozíciók egymástól.

Először is, az algoritmus rendezi az egymástól távol eső elemeket. Ezután a rés kisebb lesz, és közelebb kerülnek egymáshoz az elemek. Így egyes elemek, amelyek nincsenek megfelelő helyzetben, gyorsabban helyezhetők el, mintha a szomszédos elemekből alkészleteket készítenénk.

2.2. Egy példa

Lássuk ezt a példában a 3 és 1 hiányosságokkal és a 9 elem nem rendezett listájával:

Ha követjük a fenti leírást, akkor az első iterációban három részhalmazunk lesz 3 elemmel (ugyanazzal a színnel kiemelve):

Miután az első iterációban rendezte az egyes részhalmazokat, a lista a következőképpen néz ki:

Megjegyezhetjük, hogy bár még nincs rendezett listánk, az elemek most már közelebb vannak a kívánt pozíciókhoz.

Végül még egy sort kell elvégeznünk az egyik növekményével, és valójában ez egy alapbeillesztési rendezés. A lista rendezéséhez végrehajtandó váltási műveletek száma most kisebb, mint akkor, ha nem végeznénk az első iterációt:

2.3. A résszekvenciák kiválasztása

Mint említettük, a héjfajta egyedülálló módon választhatja ki a résszekvenciákat. Ez nehéz feladat, és vigyáznunk kell, hogy ne válasszunk túl kevés vagy túl sok hézagot. További részletek megtalálhatók a legtöbbet javasolt résszekvenciák felsorolásában.

3. Végrehajtás

Vessünk egy pillantást a megvalósításra. A Shell eredeti sorrendjét használjuk az intervallum növelésére:

N / 2, N / 4,…, 1 (folyamatosan osztva 2-vel)

Maga a megvalósítás nem túl összetett:

public void sort (int arrayToSort []) {int n = arrayToSort.length; for (int rés = n / 2; rés> 0; rés / = 2) {for (int i = rés; i = rés && arrayToSort [j - rés]> kulcs) {arrayToSort [j] = arrayToSort [j - rés ]; j - = rés; } arrayToSort [j] = kulcs; }}}

Először létrehoztunk egy résszekvenciát egy for hurokkal, majd elvégeztük a beillesztés rendezését az egyes résméretekhez.

Most könnyen tesztelhetjük módszerünket:

@Teszt nyilvános érvényesség adottUnsortedArray_whenShellSort_thenSortedAsc () {int [] input = {41, 15, 82, 5, 65, 19, 32, 43, 8}; ShellSort.sort (input); int [] várható = {5, 8, 15, 19, 32, 41, 43, 65, 82}; assertArrayEquals ("a két tömb nem egyenlő", várható, input); }

4. Komplexitás

Általában, a Shell rendezési algoritmus nagyon hatékony a közepes méretű listáknál. A bonyolultságot nehéz meghatározni, mivel nagyban függ a résszekvenciától, de az idő bonyolultsága változó TOVÁBB) és O (N ^ 2).

A legrosszabb esetben az űrbonyolultság az TOVÁBB) val vel O (1) segédtér.

5. Következtetés

Ebben az oktatóanyagban leírtuk a Shell rendezését, és bemutattuk, hogyan tudjuk megvalósítani a Java-ban.

Szokás szerint a teljes kód megtalálható a GitHubon.