Úvod do rýchleho zoradenia v Jave
Nasledujúci článok Quick Sort in Java poskytuje prehľad algoritmu rýchleho triedenia v Java. Algoritmus rýchleho zoradenia je jeden z triediacich algoritmov, ktorý je efektívny a podobný algoritmom zlučovacieho triedenia. Toto je jeden z bežne používaných algoritmov na účely triedenia v reálnom čase. Najhoršia časová zložitosť tohto algoritmu je O (n 2), priemerná časová zložitosť je O (n log n) a najlepšia časová zložitosť je O (n log n).
Priestorová zložitosť, ak O (n log n) kde n je veľkosť vstupu. Proces triedenia zahŕňa rozdelenie vstupu, rekurzívne iterácie a označenie kľúčového prvku pre každú rekurziu. Typ triedenia v tomto algoritme zahŕňa porovnanie susedných prvkov iteračným spôsobom.
Ako funguje Quick Sort v Java?
Algoritmus rýchleho zoradenia sa dá implementovať v Jave vytvorením pseudo kódu s postupnosťou krokov navrhnutých a sledovaných efektívnym spôsobom.
- Hlavný princíp algoritmu rýchleho triedenia, ktorý funguje, je založený na prístupe rozdeliť a dobyť a je tiež efektívnym algoritmom triedenia.
- Vstupné pole je rozdelené na čiastkové polia a delenie je založené na otočnom prvku, ktorý je centrálnym prvkom. Čiastkové polia na oboch stranách otočného prvku sú hlavné oblasti, v ktorých k triedeniu skutočne dochádza.
- Centrálny otočný prvok je základňa na rozdelenie poľa na dva oddiely, kde ľavá polovica prvkov poľa je menšia ako otočný prvok a pravá polovica prvkov poľa je väčšia ako otočný prvok.
- Pred zvažovaním otočného prvku to môže byť ktokoľvek z prvkov poľa. Z dôvodu ľahkého porozumenia sa to zvyčajne považuje za stredné alebo prvé alebo posledné. Otočný prvok môže byť náhodný z ktoréhokoľvek z prvkov poľa.
- V našom príklade je posledný prvok poľa považovaný za pivotný prvok, kde sa rozdelenie čiastkových polí začína od pravého konca poľa.
- Otočný prvok bude konečne vo svojej skutočnej triedenej polohe po dokončení procesu triedenia, kde hlavný proces triedenia leží v logike oblastí triediaceho algoritmu.
- Účinnosť algoritmu závisí od veľkosti čiastkových polí a od ich vyváženia. Čím viac sú čiastkové polia nevyvážené, tým viac časovej zložitosti povedie k najhoršej zložitosti.
- Výber otočných prvkov náhodným spôsobom vedie v mnohých prípadoch k najlepšej časovej zložitosti namiesto výberu konkrétneho počiatočného, koncového alebo stredného indexu ako otočných prvkov.
Príklady implementácie rýchleho zoradenia v jazyku Java
Algoritmus QuickSort bol implementovaný pomocou programovacieho jazyka Java, ako je uvedené nižšie, a výstupný kód bol zobrazený pod kódom.
- Kód spočiatku berie vstup pomocou metódy quickSortAlgo () s poľom, počiatočným indexom a konečným indexom, tj dĺžkou poľa ako argumentmi.
- Po zavolaní metódy quickSortAlgo () skontroluje, či je počiatočný index menší ako konečný index, a potom volá metódu arrayPartition (), aby získala hodnotu prvku pivot.
- Element oddielu obsahuje logiku usporiadania menších a väčších prvkov okolo otočného prvku na základe hodnôt prvkov.
- Po získaní indexu pivotných prvkov po vykonaní metódy oddielu sa metóda quickSortAlgo () nazýva sama rekurzívne, kým nie sú všetky čiastkové polia rozdelené a úplne usporiadané.
- V logike oddielu je posledný prvok priradený ako otočný prvok a prvý prvok je porovnávaný s otočným prvkom, tj posledným, kde sú prvky zamieňané na základe toho, či sú menšie alebo väčšie.
- Tento proces rekurzie nastane, kým nie sú všetky prvky poľa rozdelené a zoradené, pričom konečným výsledkom je kombinované zoradené pole.
- Prvky sa vymieňajú vnútri iterácie s opakujúcou sa slučkou iba v prípade, ak je prvok menší alebo sa rovná otočnému prvku.
- Po dokončení iteračného procesu sa posledný prvok zamení, tj hodnota otočného prvku sa presunie na ľavú stranu, takže sa vytvoria nové oddiely a ten istý proces sa opakuje vo forme rekurzie, čo má za následok sériu triediacich operácií na rôznych možných oddieloch. ako formácia čiastkových polí z daných prvkov poľa.
- Nižšie uvedený kód sa dá spustiť na akomkoľvek IDE a výstup sa dá overiť zmenou hodnoty poľa v main () Hlavná metóda sa používa iba na účely získania výstupu v konzole. Ako súčasť kódovacích štandardov Java je možné hlavnú metódu odstrániť nižšie a objekt je možné vytvoriť a nižšie je možné volať metódami, ktoré nie sú statické.
Implementácia kódu algoritmu rýchleho zoradenia v Jave
/*
* Quick Sort algorithm - Divide & Conquer approach
*/
public class QuickSortAlgorithm (
public static void main(String() args) (
int() array = ( 99, 31, 1, 3, 5, 561, 1, 342, 345, 454 );
quickSortAlgo(array, 0, array.length - 1);
for (int ar : array) (
System.out.print(ar + " ");
)
)
public static int arrayPartition(int() array, int start, int end) (
int pivot = array(end);
int i = (start - 1);
for (int ele = start; ele < end; ele++) (
if (array(ele) <= pivot) (
i++;
int swap = array(i);
array(i) = array(ele);
array(ele) = swap;
)
)
// Swapping the elements
int swap = array(i + 1);
array(i + 1) = array(end);
array(end) = swap;
return i + 1;
)
public static void quickSortAlgo(int() arrayTobeSorted, int start, int end) (
if (start < end) (
int pivot = arrayPartition(arrayTobeSorted, start, end);
quickSortAlgo(arrayTobeSorted, start, pivot - 1);
quickSortAlgo(arrayTobeSorted, pivot + 1, end);
)
)
)
Výkon:
záver
Algoritmus rýchleho triedenia je účinný, ale nie príliš stabilný v porovnaní s inými technikami triedenia. Účinnosť algoritmov rýchleho zoradenia klesá v prípade väčšieho počtu opakovaných prvkov, čo je nevýhoda. V tomto algoritme rýchleho triedenia je optimalizovaná zložitosť priestoru.
Odporúčané články
Toto je príručka pre rýchle zoradenie v jazyku Java. Tu diskutujeme o tom, ako Quick Sort funguje v Jave, spolu s príkladom a implementáciou kódu. Viac informácií nájdete aj v ďalších navrhovaných článkoch -
- Usporiadanie haldy v Jave
- Čo je binárny strom v Jave?
- Bitová manipulácia v Jave
- Prehľad zlúčenia zoradenia v JavaScripte
- Prehľad rýchleho zoradenia v JavaScripte
- Halda Zoradiť v Pythone
- Top 6 triediaci algoritmus v JavaScripte