Všetko, čo potrebujete vedieť o Quicksort v C ++

Existuje nepreberné množstvo triediacich algoritmov. Nájdenie vhodného riešenia pre vašu aplikáciu je úloha, ktorá si vyžaduje krátke pochopenie faktorov, ako sú výkon, časová zložitosť, dĺžka kódu atď. Konkrétneho algoritmu. V tomto príspevku sa pozrieme na všetky základné koncepty potrebné na implementáciu Quicksort v C ++ v nasledujúcom poradí:

• Pochopenie algoritmu Quicksort
• Pseudokód pre Quicksort
• Program Quicksort v C ++
• Rýchla trieda časovej zložitosti

Pochopenie algoritmu Quicksort

Rovnako ako Zlúčiť zoradenie , Quicksort sa riadi stratégiou rozdelenia a dobytia. Použitím stratégie rozdelenia a dobývania rozdelíme problém na mnoho čiastkových problémov a riešime ich rekurzívne. Najprv pochopíme celý proces krok za krokom a potom pomocou príkladu rozvinieme hlboké pochopenie celého procesu.

rozdiel medzi hashmapou a hashtable

1. Najskôr od používateľa požiadame o netriedené pole.

2. Akonáhle máme naše netriedené pole, musíme z neho zvoliť otočnú hodnotu. Môžeme zvoliť ľubovoľnú hodnotu.

   
   
   

3. Akonáhle vyberieme otočný bod, potom musíme usporiadať ďalšie prvky poľa tak, aby sa všetky prvky menšie ako hodnota otočenia umiestnili napravo od hodnoty otočenia a všetky prvky väčšie ako otočný bod hodnota sa má umiestniť napravo od kontingenčnej hodnoty.

4. Krok 3 vykonávame, kým nedostaneme zoradené pole.

Pozrime sa teraz na príklad a implementujme algoritmus a pozrime sa, ako to funguje.

Dobrý deň [5, 4, 1, 11, 9, 6, 2, 3], v tomto príklade budeme pivot vždy považovať za prvok úplne vpravo na zozname.

Prejdime si každý krok a pochopme logiku, ktorú sme použili na vyriešenie problému.

• Najskôr sme vybrali „3“ ako náš otočný čap a usporiadali sme všetky prvky menšie ako „3“ vpravo a všetky prvky väčšie ako „3“ vpravo.

• V tomto okamihu máme 2 podproblémy. Najprv vyriešime podproblém vpravo. Jeden sme vybrali ako náš otočný čap a umiestnili sme „2“ doprava.

• Na vyriešenie druhého čiastkového problému zvolíme ako náš otočný bod „6“ a umiestnime prvky, ako sme už diskutovali.

• Máme ďalšie 2 podproblémy. Prvý je vyriešený výberom 4 ako čapu a druhý je vyriešený výberom 9 ako čapu. Nakoniec máme zoradené pole s prvkami umiestnenými v indexe podčiarknutia.

Poznámka- Dôležitým bodom na pochopenie je, že všetky operácie prebiehajú v rovnakom poli. Nové polia sa nevytvárajú.

Pseudokód pre Quicksort v C ++

QuickSort (pole [], start_index, end_index) {if (start_index
 Program Quicksort v C ++ 
Pochopili sme algoritmus a hlboko sme porozumeli jeho fungovaniu. Implementujme Quicksort v C ++ a napíšme program na triedenie poľa.
#include using namespace std void swap_elements (int * a, int * b) {int temp = * a * a = * b * b = temp} int partition (int array [], int start_index, int end_index) {int pivot = pole [end_index] int i = (start_index - 1) pre (int j = start_index j<= end_index- 1 j++) { if (array[j] <= pivot) { i++ swap_elements(&array[i], &array[j]) } } swap_elements(&array[i + 1], &array[end_index]) return (i + 1) } void quickSort(int array[], int start_index, int end_index) { if (start_index < end_index) { int partition_index = partition(array, start_index, end_index) quickSort(array, start_index, partition_index - 1) quickSort(array, partition_index + 1, end_index) } } void printArray(int array[], int number) { int i cout<<'Sorted Array: ' for (i = 0 i < number i++) cout << array[i] << ' ' cout << endl } int main() { int Hello[30] int i int NumberofElements cout<>NumberofElements náklady<<'Enter the elements one by one: ' for(i=0i>Hello [i]} quickSort (Hello, 0, NumberofElements-1) printArray (Hello, NumberofElements) return 0}
 Výkon: 
 Časová zložitosť 
Poďme si povedať o najdôležitejšom aspekte každého algoritmu triedenia, teda o časovej zložitosti. Hovorí nám o výkonnosti algoritmu v rôznych scenároch. Tieto hodnoty nám môžu pomôcť pri rozhodovaní, či môžeme tento algoritmus použiť pre našu aplikáciu.
 Najlepší prípad O (n)
 Priemerný prípad (neprihlásiť sa)
 V najhoršom prípade- O (n2)
Týmto sa dostávame na koniec tohto článku o Quicksorte v C ++. Ak sa chcete dozvedieť viac, pozrite si   Edureka, dôveryhodná online vzdelávacia spoločnosť. Výcvikový a certifikačný kurz Edureka Java J2EE a SOA je navrhnutý tak, aby vás vyškolil na základné aj pokročilé koncepty Java spolu s rôznymi rámcami Java, ako je Hibernate & Spring.
 Máte na nás otázku? Uveďte to prosím v sekcii komentárov tohto blogu a my sa vám ozveme čo najskôr.