Menu

QuickSort In Java - Algoritmus, ilustrace a implementace

  • Hlavní
  • Jiný
  • QuickSort In Java - Algoritmus, ilustrace a implementace

quicksort java algorithm

Vyzkoušejte Náš Nástroj Pro Odstranění Problémů

Tento výukový program vysvětluje algoritmus Quicksort v Javě, jeho ilustrace, implementaci QuickSort v Javě pomocí příkladů kódu:

Technika třídění Quicksort je široce používána v softwarových aplikacích. Quicksort používá strategii rozdělení a dobývání, jako je sloučení.

V algoritmu quicksort je nejprve vybrán speciální prvek zvaný „pivot“ a dotyčné pole nebo seznam je rozdělen do dvou podmnožin. Rozdělené podskupiny mohou nebo nemusí mít stejnou velikost.

=> Přečtěte si řadu Easy Java Training Series.

Technika QuickSort v Javě

Příčky jsou takové, že všechny prvky menší než otočný prvek jsou směrem k levé části otočného prvku a prvky větší než otočný prvek jsou napravo od otočného prvku. Rutina Quicksort rekurzivně třídí dva dílčí seznamy. Quicksort pracuje efektivně a také rychleji i pro větší pole nebo seznamy.

Co se naučíte:

Quicksort Partition Java

Dělení je klíčovým procesem techniky Quicksort. Co je tedy rozdělení na oddíly?

Vzhledem k poli A zvolíme hodnotu x nazvanou pivot tak, že všechny prvky menší než x jsou před x a všechny prvky větší než x jsou po x.

software ke stažení videí na trubici

Pivotní hodnota může být některá z následujících:

  • První prvek v poli
  • Poslední prvek v poli
  • Střední prvek v poli
  • Libovolný náhodný prvek v poli

Tato pivotní hodnota je poté umístěna na správné místo v poli rozdělením pole. Výstupem procesu „rozdělení“ je tedy hodnota pivot na jeho správné pozici a prvky menší než pivot vlevo a prvky větší než pivot vpravo.

Zvažte následující diagram, který vysvětluje proces vytváření oddílů.

proces dělení

Výše uvedený diagram ukazuje proces dělení pole opakovaným výběrem posledního prvku v poli jako otočného čepu. Na každé úrovni si všimněte, že rozdělujeme pole do dvou dílčích polí umístěním otočného čepu do správné polohy.

Dále uvádíme seznam algoritmů a pseudokódů pro techniku ​​rychlého třídění, která zahrnuje také rutinu oddílu.

Quicksort Algorithm Java

Obecný algoritmus pro rychlé řazení je uveden níže.

quicksort(Arr, low, high) begin Declare array Arr(N) to be sorted low = 1st element; high = last element; pivot if(low

Níže je uveden pseudokód pro techniku ​​rychlého řazení.

Pseudokód pro rychlé třídění

Následuje pseudokód pro techniku ​​rychlého řazení. Všimněte si, že jsme poskytli pseudokód pro rutinu rychlého řazení a rozdělení.

//pseudocode for quick sort main algorithm procedure quickSort(arr(), low, high) arr = list to be sorted low – first element of the array high – last element of array begin if (low

Ilustrace

Podívejme se na ilustraci algoritmu quicksort. Jako příklad si vezměte následující pole. Zde jsme jako pivot vybrali poslední prvek.

Jak je znázorněno, první prvek je označen jako nízký a poslední prvek je vysoko.

Dotazy a odpovědi administrátora salesforce na rozhovor

Ilustrace algoritmu Quicksort

Jak je zřejmé z výše uvedeného obrázku, existují dva ukazatele, vysoký a nízký, které ukazují na poslední a první prvky pole. Oba tyto ukazatele se během postupu rychlého řazení přesouvají.

Když se prvek, na který ukazuje nízký ukazatel, stává větším než otočný prvek a prvek, na který ukazuje vysoký ukazatel, je menší než otočný prvek, vyměníme si prvky, na které ukazuje nízký a vysoký ukazatel, a každý ukazatel se posune o 1 pozici.

Výše uvedené kroky se provádějí, dokud se oba ukazatele v poli nepřekříží. Jakmile se otočí, otočný prvek získá správnou pozici v poli. V tomto okamžiku je pole rozděleno na oddíly a nyní můžeme každé dílčí pole řadit samostatně rekurzivním použitím algoritmu rychlého řazení na každé dílčí pole.

Implementace Quicksort v Javě

Techniku ​​QuickSort lze v Javě implementovat pomocí rekurze nebo iterace. V této části uvidíme obě tyto techniky.

Rekurzivní Quicksort

Víme, že základní technika rychlého třídění ilustrovaná výše používá pro třídění pole rekurzi. V rekurzivním quicksortu po rozdělení pole je rutina quicksortu volána rekurzivně, aby se seřadila dílčí pole.

Níže uvedená implementace demonstruje techniku ​​rychlého řazení pomocí rekurze.

import java.util.*; class QuickSort { //selects last element as pivot, pi using which array is partitioned. int partition(int intArray(), int low, int high) { int pi = intArray(high); int i = (low-1); // smaller element index for (int j=low; j

Výstup:

Původní pole: (4, -1, 6, 8, 0, 5, -3)
Řazené pole: (-3, -1, 0, 4, 5, 6, 8)

Rekurzivní quicksort - výstup

Iterativní Quicksort

V iteračním rychlém řazení používáme pomocný zásobník k umístění přechodných parametrů namísto použití rekurze a řazení oddílů.

Následující program Java implementuje iterativní quicksort.

import java.util.*; class Main { //partitions the array around pivot=> last element static int partition(int numArray(), int low, int high) { int pivot = numArray(high); // smaller element index int i = (low - 1); for (int j = low; j <= high - 1; j++) { // check if current element is less than or equal to pivot if (numArray(j) <= pivot) { i++; // swap the elements int temp = numArray(i); numArray(i) = numArray(j); numArray(j) = temp; } } // swap numArray(i+1) and numArray(high) (or pivot) int temp = numArray(i + 1); numArray(i + 1) = numArray(high); numArray(high) = temp; return i + 1; } //sort the array using quickSort static void quickSort(int numArray(), int low, int high) { //auxillary stack int() intStack = new int(high - low + 1); // top of stack initialized to -1 int top = -1; // push initial values of low and high to stack intStack(++top) = low; intStack(++top) = high; // Keep popping from stack while is not empty while (top>= 0) { // Pop h and l high = intStack(top--); low = intStack(top--); // Set pivot element at its correct position // in sorted array int pivot = partition(numArray, low, high); // If there are elements on left side of pivot, // then push left side to stack if (pivot - 1 > low) { intStack(++top) = low; intStack(++top) = pivot - 1; } // If there are elements on right side of pivot, // then push right side to stack if (pivot + 1

Výstup:

Původní pole: (3, 2, 6, -1, 9, 1, -6, 10, 5)
Řazené pole: (- 6, -1, 1, 2, 3, 6, 9, 10, 5)

Iterativní quicksort - výstup

Často kladené otázky

Otázka č. 1) Jak funguje Quicksort?

Odpovědět: Quicksort používá strategii rozdělení a dobývání. Quicksort nejprve rozděluje pole na vybraný otočný prvek a generuje dílčí pole, která jsou rekurzivně tříděna.

Otázka 2) Jaká je časová složitost Quicksortu?

Odpovědět: Časová složitost rychlého třídění je v průměru O (nlogn). V nejhorším případě je to O (n ^ 2) stejné jako výběrové řazení.

Otázka č. 3) Kde se používá Quicksort?

Odpovědět: Quicksort se většinou používá v rekurzivních aplikacích. Quicksort je součástí C-knihovny. Také téměř programovací jazyky, které používají integrované třídění, implementují quicksort.

který vr pracuje s Xbox One

Otázka č. 4) Jaká je výhoda Quicksortu?

Odpovědět:

  • Quicksort je efektivní algoritmus, který dokáže snadno seřadit i obrovský seznam prvků.
  • Je to místní řazení, a proto nepotřebuje další prostor ani paměť.
  • Je široce používán a poskytuje efektivní způsob třídění datových souborů jakékoli délky.

Otázka č. 5) Proč je Quicksort lepší než sloučení?

Odpovědět: Hlavním důvodem, proč je quicksort lepší než sloučení, je to, že quicksort je metoda třídění na místě a nevyžaduje další paměťový prostor. Sloučit řazení vyžaduje další paměť pro mezilehlé třídění.

Závěr

Quicksort je považován za nejlepší třídicí algoritmus hlavně kvůli jeho efektivnosti třídění i obrovské datové sady v čase O (nlogn).

Quicksort je také řazení na místě a nevyžaduje další místo v paměti. V tomto kurzu jsme viděli rekurzivní a iterativní implementaci quicksortu.

V našem nadcházejícím tutoriálu budeme pokračovat v metodách řazení v Javě.

=> Prohlédněte si příručku Java Beginners Guide zde.

Doporučené čtení

^