streamalism.org

1. Úvod

V tomto článku sa ponoríme do algoritmus triedenia segmentov. Začneme rýchlym trochu teórie, skôr ako začnete s implementáciou Java popri testovaní jednotky naše riešenie. Nakoniec budeme pozri sa na časovú zložitosť triedenia vedra.

2. Teória triedenia vedra

Triedenie na segment, niekedy známe ako triedenie na kôš, je špecifický algoritmus triedenia. Triedenie funguje tak, že prvky, ktoré chceme triediť, sa distribuuje do niekoľkých individuálne triedených segmentov. Týmto spôsobom môžeme znížiť počet porovnaní medzi prvkami a pomôcť tak skrátiť čas triedenia.

Poďme sa rýchlo pozrieť na kroky potrebné na vykonanie triedenia segmentov:

1. Vytvorte pole našich pôvodne prázdnych segmentov
2. Distribuujte naše prvky do príslušných vedier
3. Triedte každý vedro
4. Spojte zoradené segmenty dohromady a vytvorte tak úplný zoznam

3. Implementácia Java

Aj keď tento algoritmus nie je špecifický pre jazyk, implementujeme triedenie v Jave. Prejdime si vyššie uvedený zoznam krok za krokom a napíšeme kód na triedenie zoznamu celých čísel.

3.1. Nastavenie lopaty

Najprv my je potrebné určiť hashovací algoritmus rozhodnúť, ktoré z našich prvkov sa umiestnia do ktorého vedra:

private int hash (int i, int max, int numberOfBuckets) {return (int) ((double) i / max * (numberOfBuckets - 1)); }

S našou definovanou hashovou metódou to teraz môžeme zadajte počet zásobníkov ako druhá odmocnina veľkosti vstupného zoznamu:

final int numberOfBuckets = (int) Math.sqrt (initialList.size ()); Zoznam vedierka = nový ArrayList (numberOfBuckets); for (int i = 0; i <numberOfBuckets; i ++) {buckets.add (new ArrayList ()); }

Nakoniec potrebujeme krátku metódu na určenie maximálneho celého čísla v našom vstupnom zozname:

private int findMax (vstup do zoznamu) {int m = Integer.MIN_VALUE; pre (int i: vstup) {m = Math.max (i, m); } návrat m; }

3.2. Distribúcia prvkov

Teraz, keď máme definované naše segmenty, môžeme distribuujte každý prvok nášho vstupného zoznamu do jeho príslušného segmentu pomocou hash metóda:

int max = findMax (initialList); pre (int i: initialList) {buckets.get (hash (i, max, numberOfBuckets)). add (i); } 

3.3. Triedenie jednotlivých segmentov

S našimi segmentami definovanými a plnými celých čísel, použijeme a Komparátor triediť ich:

Komparátor komparátor = Comparator.naturalOrder (); pre (List bucket: buckets) {bucket.sort (komparátor); }

3.4. Zreťazenie našich vedier

Nakoniec musíme naše vedrá spojiť, aby sme vytvorili jednotný zoznam. Pretože sú naše segmenty zoradené, stačí, aby sme každý segment prekonali iba raz a pridali prvky do hlavného zoznamu:

Zoznam triedenýArray = nový LinkedList (); pre (List bucket: buckets) {sortArray.addAll (bucket); } návrat sortArray;

4. Testovanie nášho kódexu

Po dokončení našej implementácie napíšeme rýchly test jednotky, aby sme sa ubezpečili, že funguje podľa očakávaní:

Triedič BucketSorter = nový IntegerBucketSorter (); Zoznam netriedený = Arrays.asList (80,50,60,30,20,10,70,0,40,500,600,602,200,15); Očakávaný zoznam = Arrays.asList (0,10,15,20,30,40,50,60,70,80,200,500,600,602); Zoznam zoradený = sorter.sort (netriedený); assertEquals (očakávané, zoradené);

5. Časová zložitosť

Ďalej sa poďme rýchlo pozrieť na časovú zložitosť vykonávania triedenia segmentov.

5.1. Najhorší prípad

V najhoršom prípade by sme to našli všetky naše prvky v rovnakom segmente a v opačnom poradí. Ak nastane tento prípad, zredukujeme naše triedenie na jednoduché triedenie, v ktorom sa každý prvok porovnáva s každým iným prvkom, čím sa získa časová zložitosť O (n²).

5.2. Priemerný prípadový scenár

V našom priemernom prípade zistíme, že prvky sú relatívne rovnomerne rozdelené medzi naše vstupné segmenty. Pretože každý z našich krokov vyžaduje iba jednu iteráciu cez naše vstupné segmenty, zistíme, že náš segment je zoradený sa dokončí v O (n) čase.

6. Záver

V tomto článku sme videli, ako implementovať triedenie segmentov v Jave. Pozreli sme sa tiež na časovú zložitosť algoritmu triedenia segmentov.

Ako vždy, kód zobrazený v tomto článku je k dispozícii na GitHub.