Úvod do rychlého třídění v Javě

Následující článek Rychlé třídění v Javě poskytuje přehled algoritmu rychlého třídění v jazyce Java. Algoritmus rychlého třídění je jeden z třídicích algoritmů, který je účinný a podobný algoritmu sloučeného třídění. Toto je jeden z nejčastěji používaných algoritmů pro účely třídění v reálném čase. Nejhorší složitost tohoto algoritmu je O (n 2), průměrná časová složitost je O (n log n) a nejlepší časová složitost je O (n log n).

Složitost prostoru, pokud O (n log n) kde n je velikost vstupu. Proces třídění zahrnuje rozdělení vstupu, rekurzivní iterace a označení klíčového prvku pro každou rekurzi. Typ třídění v tomto algoritmu zahrnuje iterativní porovnání sousedních prvků.

Jak funguje Quick Sort v Javě?

Algoritmus rychlého třídění může být implementován v Javě vytvořením pseudo kódu se sledem kroků navržených a následovaných efektivním způsobem.

  1. Hlavní princip algoritmu rychlého třídění, který funguje, je založen na přístupu rozdělit a dobýt a je také efektivním algoritmem třídění.
  2. Vstupní pole je rozděleno na dílčí pole a rozdělení je založeno na otočném prvku, který je centrálním prvkem. Dílčí pole na obou stranách otočného prvku jsou hlavní oblasti, ve kterých k třídění skutečně dochází.
  3. Centrální otočný prvek je základna pro rozdělení pole na dvě oddíly, kde levá polovina prvků pole je menší než otočný prvek a pravá polovina prvků pole je větší než otočný prvek.
  4. Před zvažováním otočného prvku to může být kdokoli z prvků pole. To je obvykle považováno za střední nebo první nebo poslední z důvodu snadnosti porozumění. Otočný prvek může být náhodný z kteréhokoli z prvků pole.
  5. V našem příkladu je poslední prvek pole považován za pivotní prvek, kde dělení dílčích polí začíná od pravého konce pole.
  6. Nakonec bude otočný prvek ve své skutečné tříděné poloze po dokončení procesu třídění, kde hlavní proces třídění spočívá v logice oddílu třídicího algoritmu.
  7. Účinnost algoritmu závisí na velikosti dílčích polí a na jejich vyváženosti. Čím více jsou dílčí pole nevyvážená, tím více časová složitost povede k nejhorší složitosti.
  8. Výběr otočných prvků náhodným způsobem vede v mnoha případech k nejlepší časové složitosti namísto výběru konkrétních počátečních, koncových nebo středních indexů jako otočných prvků.

Příklady implementace rychlého třídění v Javě

Algoritmus QuickSort byl implementován pomocí programovacího jazyka Java, jak je uvedeno níže, a výstupní kód byl zobrazen pod kódem.

  1. Kód zpočátku bere vstup pomocí metody quickSortAlgo () s polem, počátečním indexem a konečným indexem, tj. Délkou pole jako argumenty.
  2. Po volání metody quickSortAlgo () zkontroluje, zda je počáteční index menší než konečný index, a poté volá metodu arrayPartition (), aby získala hodnotu prvku pivot.
  3. Prvek oddílu obsahuje logiku uspořádání menších a větších prvků kolem otočného prvku na základě hodnot prvků.
  4. Po získání indexu pivotních elementů po provedení metody rozdělení je metoda quickSortAlgo () volána sama rekurzivně, dokud nejsou všechna dílčí pole rozdělena a kompletně tříděna.
  5. V logice oddílu je poslední prvek přiřazen jako otočný prvek a první prvek je porovnán s otočným prvkem, tj. Posledním, kde jsou prvky zaměněny na základě toho, zda jsou menší nebo větší.
  6. K tomuto procesu rekurze dochází, dokud nejsou všechny prvky pole rozděleny a tříděny, přičemž konečným výsledkem je kombinované tříděné pole.
  7. Prvky jsou zaměněny uvnitř iterace smyčky pouze v případě, že je prvek menší nebo stejný jako otočný prvek.
  8. Po dokončení iteračního procesu je poslední prvek zaměněn, tj. Hodnota otočného prvku je přesunuta na levou stranu, takže jsou vytvořeny nové oddíly a stejný proces se opakuje ve formě rekurze, což má za následek řadu třídicích operací na různých možných oddílech. jako formace dílčích polí z daných prvků pole.
  9. Níže uvedený kód lze spustit na libovolném IDE a výstup lze ověřit změnou hodnoty pole v main () Hlavní metoda se používá pouze za účelem získání výstupu v konzole. Jako součást standardů kódování Java lze hlavní metodu odstranit níže a objekt lze vytvořit a metody níže lze volat tak, že se stanou nestatickými.

Implementace kódu algoritmu rychlého třídění v Javě

/*
* 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ýstup:

Závěr

Algoritmus rychlého třídění je účinný, ale není příliš stabilní ve srovnání s jinými třídicími technikami. Účinnost algoritmů rychlého třídění klesá v případě většího počtu opakovaných prvků, což je nevýhoda. Prostorová složitost je optimalizována tímto algoritmem rychlého řazení.

Doporučené články

Toto je průvodce rychlým tříděním v Javě. Zde diskutujeme, jak Quick Sort pracuje v Javě, spolu s příkladem a implementací kódu. Další informace naleznete také v dalších navrhovaných článcích -

  1. Hromadné řazení v Javě
  2. Co je binární strom v Javě?
  3. Bitová manipulace v Javě
  4. Přehled slučovacího řazení v JavaScriptu
  5. Přehled rychlého třídění v JavaScriptu
  6. Haldy Seřadit v Pythonu
  7. Top 6 algoritmů třídění v JavaScriptu

Kategorie:

Vývoj softwaru