Menu

QuickSort In Java - Algoritmus, ilustrácia a implementácia

  • Hlavná
  • Iné
  • QuickSort In Java - Algoritmus, ilustrácia a implementácia

quicksort java algorithm

Vyskúšajte Náš Nástroj Na Odstránenie Problémov

Tento výukový program vysvetľuje algoritmus Quicksort v Jave, jeho ilustrácie, implementáciu QuickSort v Jave pomocou príkladov kódu:

Technika triedenia Quicksort je široko používaná v softvérových aplikáciách. Quicksort používa stratégiu rozdelenia a dobývania, ako je napríklad zlúčenie.

V algoritme quicksort sa najskôr vyberie špeciálny prvok s názvom „pivot“ a príslušné pole alebo zoznam sa rozdelí na dve podmnožiny. Rozdelené podskupiny môžu alebo nemusia mať rovnakú veľkosť.

b strom vs b + strom

=> Prečítajte si sériu Easy Java Training Series.

Technika QuickSort v Jave

Priečky sú také, že všetky prvky menšie ako otočný prvok sú smerom doľava od otočného čapu a prvky väčšie ako otočný čap sú vpravo od otočného čapu. Rutina Quicksort rekurzívne triedi dva podzoznamy. Quicksort pracuje efektívne a tiež rýchlejšie aj pre väčšie polia alebo zoznamy.

Čo sa dozviete:

Quicksort Partition Java

Rozdelenie na oddiely je kľúčovým procesom techniky Quicksort. Čo je to teda rozdelenie?

Vzhľadom na pole A vyberieme hodnotu x nazvanú pivot tak, aby všetky prvky menšie ako x boli pred x a všetky prvky väčšie ako x boli za x.

Kontingenčnou hodnotou môže byť ktorákoľvek z nasledujúcich možností:

  • Prvý prvok v poli
  • Posledný prvok v poli
  • Stredný prvok v poli
  • Akýkoľvek náhodný prvok v poli

Táto pivotná hodnota sa potom umiestni na správne miesto v poli rozdelením poľa. Výstupom procesu „rozdelenia“ je teda hodnota otočenia na svojej správnej pozícii a prvky menšie ako otočenie vľavo a prvky väčšie ako otočenie vpravo.

Zvážte nasledujúci diagram, ktorý vysvetľuje proces rozdelenia na oddiely.

proces rozdelenia

Vyššie uvedený diagram ukazuje proces rozdelenia poľa opakovaným výberom posledného prvku v poli ako otočného bodu. Na každej úrovni si všimnite, že pole je rozdelené do dvoch podriadených polí umiestnením otočného čidla do správnej polohy.

Ďalej uvádzame zoznam algoritmov a pseudokódov pre techniku ​​rýchleho triedenia, ktorá obsahuje aj rutinu oddielov.

Quicksort Algorithm Java

Všeobecný algoritmus pre rýchle triedenie je uvedený nižšie.

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

Ďalej je uvedený pseudokód pre techniku ​​rýchleho triedenia.

Pseudokód pre rýchle triedenie

Nasleduje pseudokód pre techniku ​​rýchleho triedenia. Upozorňujeme, že sme poskytli pseudokód pre rutinu rýchleho triedenia a rozdelenia.

//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

Ilustrácia

Pozrime sa na ilustráciu algoritmu quicksort. Vezmite si nasledujúce pole ako príklad. Tu sme vybrali posledný prvok ako otočný.

Ako je znázornené, prvý prvok je označený ako nízky a posledný prvok je vysoko.

Ilustrácia algoritmu Quicksort

Ako je zrejmé z vyššie uvedenej ilustrácie, existujú dva ukazovatele, vysoký a nízky, ktoré smerujú k poslednému a prvému prvku poľa. Oba tieto ukazovatele sa posúvajú, ako postupuje rýchly rad.

Keď sa prvok nasmerovaný dolným ukazovateľom stane väčším ako otočný prvok a prvok nasmerovaný horným ukazovateľom je menší ako otočný prvok, vymeníme prvky nasmerované dolným a vysokým ukazovateľom a každý ukazovateľ sa posunie o 1 pozíciu.

Vyššie uvedené kroky sa uskutočňujú dovtedy, kým sa oba ukazovatele v poli nekrížia. Po prekročení získa otočný prvok svoju správnu pozíciu v poli. V tomto okamihu je pole rozdelené na oddiely a teraz môžeme každé čiastkové pole triediť nezávisle rekurzívnym použitím algoritmu rýchleho triedenia na každé z čiastkových polí.

Quicksort Implementácia v Jave

Techniku ​​QuickSort je možné v Jave implementovať pomocou rekurzie alebo iterácie. V tejto časti uvidíme obe tieto techniky.

Rekurzívny Quicksort

Vieme, že základná technika rýchleho triedenia znázornená vyššie používa na triedenie poľa rekurziu. V rekurzívnom quicksorte po rozdelení poľa sa rutina quicksortu nazýva rekurzívne na triedenie podradených polí.

Nasledujúca implementácia demonštruje techniku ​​rýchleho triedenia pomocou rekurzie.

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ýkon:

Pôvodné pole: (4, -1, 6, 8, 0, 5, -3)
Zoradené pole: (-3, -1, 0, 4, 5, 6, 8)

Rekurzívny quicksort - výstup

Iteračný Quicksort

V iteračnom quicksort používame pomocný zásobník na umiestňovanie prechodných parametrov namiesto použitia oblastí na rekurziu a triedenie.

Nasledujúci program Java implementuje iteračný 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ýkon:

Originálne pole: (3, 2, 6, -1, 9, 1, -6, 10, 5)
Zoradené pole: (- 6, -1, 1, 2, 3, 6, 9, 10, 5)

Iteračný quicksort - výstup

často kladené otázky

Otázka 1) Ako funguje Quicksort?

Odpoveď: Quicksort používa stratégiu rozdelenia a dobytia. Quicksort najskôr rozdelí pole okolo vybraného otočného prvku a vygeneruje čiastkové polia, ktoré sú rekurzívne zoradené.

Otázka 2) Aká je časová náročnosť Quicksortu?

Odpoveď: Časová zložitosť rýchleho triedenia je v priemere O (nlogn). V najhoršom prípade je to O (n ^ 2) rovnaké ako pri výbere.

Otázka 3) Kde sa používa Quicksort?

Odpoveď: Quicksort sa väčšinou používa v rekurzívnych aplikáciách. Quicksort je súčasťou C-knižnice. Takmer takmer programovacie jazyky, ktoré používajú zabudované triedenie, tiež implementujú quicksort.

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

Odpoveď:

  • Quicksort je efektívny algoritmus, ktorý dokáže ľahko triediť aj obrovský zoznam prvkov.
  • Je to lokálne triedenie, a preto nepotrebuje ďalší priestor ani pamäť.
  • Je široko používaný a poskytuje efektívny spôsob triedenia súborov dát akejkoľvek dĺžky.

Otázka č. 5) Prečo je Quicksort lepší ako pri zlúčení?

Odpoveď: Hlavným dôvodom, prečo je quicksort lepší ako triedenie zlúčenia, je ten, že quicksort je metóda triedenia na mieste a nevyžaduje ďalší pamäťový priestor. Zlúčenie zoradenia vyžaduje pre medziradenie ďalšiu pamäť.

Záver

Quicksort je považovaný za najlepší triediaci algoritmus hlavne kvôli jeho efektivite na triedenie aj obrovskej množiny dát v čase O (nlogn).

Quicksort je tiež triedenie na mieste a nevyžaduje ďalšie miesto v pamäti. V tomto tutoriáli sme videli rekurzívnu a iteratívnu implementáciu quicksortu.

V našom pripravovanom výučbe budeme pokračovať v metódach triedenia v Jave.

=> Tu si pozrite príručku Java Beginners Guide.

Odporúčané čítanie

^