quick sort c with examples
Quicksort v C ++ s ilustráciou.
Quicksort je široko používaný algoritmus triedenia, ktorý vyberá konkrétny prvok nazývaný „pivot“ a rozdeľuje pole alebo zoznam, ktorý sa má zoradiť na dve časti založené na tomto pivot s0, takže prvky menšie ako pivot sú naľavo od zoznamu a prvky napravo od zoznamu sú väčšie ako čap.
Zoznam je teda rozdelený do dvoch podlistov. Podzoznamy nemusia byť potrebné pre rovnakú veľkosť. Potom sa program Quicksort rekurzívne volá, aby tieto dva podlisty zoradil.
=> Tu si pozrite perfektného školiaceho sprievodcu pre C ++.
Čo sa dozviete:
- Úvod
- Všeobecný algoritmus
- Pseudokód pre Quicksort
- Ilustrácia
- Príklad C ++
- Príklad Java
- Analýza zložitosti algoritmu Quicksort
- 3-smerný Quicksort
- Randomizovaný Quicksort
- Quicksort vs. Merge Sort
- Záver
- Odporúčané čítanie
Úvod
Quicksort funguje efektívne aj rýchlejšie aj pre väčšie polia alebo zoznamy.
V tomto výučbe sa dozvieme viac o práci programu Quicksort spolu s príkladmi programovania algoritmu quicksort.
Ako pivotnú hodnotu môžeme zvoliť prvú, poslednú alebo strednú hodnotu alebo ľubovoľnú náhodnú hodnotu. Všeobecná myšlienka je, že nakoniec sa pivotná hodnota umiestni na správne miesto v poli presunutím ostatných prvkov v poli doľava alebo doprava.
Všeobecný algoritmus
Všeobecný algoritmus pre Quicksort je uvedený nižšie.
quicksort(A, low, high) begin Declare array A[N] to be sorted low = 1st element; high = last element; pivot if(low Pozrime sa teraz na pseudokód pre techniku Quicksort.
Pseudokód pre Quicksort
//pseudocode for quick sort main algorithm procedure quickSort(arr[], low, high) arr = list to be sorted low – first element of array high – last element of array begin if (low Fungovanie oddielového algoritmu je popísané nižšie na príklade.
Na tejto ilustrácii považujeme posledný prvok za otočný. Vidíme, že pole je postupne rozdelené okolo otočného prvku, kým v poli nebudeme mať jeden prvok.
Teraz uvádzame ilustráciu Quicksortu, aby sme lepšie pochopili tento koncept.
Ilustrácia
Pozrime sa na ilustráciu algoritmu quicksort. Zvážte nasledujúce pole s posledným prvkom ako otočným. Prvý prvok je tiež označený ako nízky a posledný prvok je vysoko.
Z ilustrácie to vidíme, že posúvame ukazovatele vysoko a nízko na oboch koncoch poľa. Kedykoľvek dolné body ukazujú na prvok väčší ako otočný čap a vysoké ukazujú na prvok menší ako čap, potom vymeníme polohy týchto prvkov a posúvame dolný a vysoký ukazovateľ v ich príslušných smeroch.
ako vytvoriť zoznam celých čísel v jave
Toto sa deje dovtedy, kým sa dolný a vysoký ukazovateľ navzájom krížia. Akonáhle sa skrížia, otočný prvok sa umiestni do svojej správnej polohy a pole sa rozdelí na dve časti. Potom sú obidve tieto podrady zoradené nezávisle pomocou rekurzívneho rýchleho triedenia.
Príklad C ++
Ďalej je uvedená implementácia algoritmu Quicksort v C ++.
#include using namespace std; // Swap two elements - Utility function void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; } // partition the array using last element as pivot int partition (int arr[], int low, int high) { int pivot = arr[high]; // pivot int i = (low - 1); for (int j = low; j <= high- 1; j++) { //if current element is smaller than pivot, increment the low element //swap elements at i and j if (arr[j] <= pivot) { i++; // increment index of smaller element swap(&arr[i], &arr[j]); } } swap(&arr[i + 1], &arr[high]); return (i + 1); } //quicksort algorithm void quickSort(int arr[], int low, int high) { if (low < high) { //partition the array int pivot = partition(arr, low, high); //sort the sub arrays independently quickSort(arr, low, pivot - 1); quickSort(arr, pivot + 1, high); } } void displayArray(int arr[], int size) { int i; for (i=0; i < size; i++) cout< Výkon:
Vstupné pole
12 23 3 43 51 35 19 45
Pole zoradené podľa rýchleho triedenia
3 12 19 23 35 43 45 51
Tu máme niekoľko rutín, ktoré sa používajú na rozdelenie poľa a rekurzívne volanie quicksortu na triedenie oddielu, základné funkcie quicksortu a pomocné funkcie na zobrazenie obsahu poľa a zodpovedajúce zámeny týchto dvoch prvkov.
Najskôr zavoláme funkciu quicksort so vstupným poľom. Vo vnútri funkcie quicksort nazývame funkciu oddielu. Vo funkcii rozdelenia použijeme posledný prvok ako otočný prvok pre pole. Keď sa rozhodne o otočení, pole sa rozdelí na dve časti a potom sa vyvolá funkcia quicksort na nezávislé triedenie obidvoch podradených polí.
Keď sa funkcia quicksort vráti, pole je zoradené tak, aby bol prvok otočného prvku na správnom mieste a prvky menšie ako bod otočenia sú vľavo od bodu otáčania a prvky väčšie ako bod otáčania sú vpravo od bodu otáčania.
Ďalej implementujeme algoritmus quicksort v Jave.
Príklad Java
// Quicksort implementation in Java class QuickSort { //partition the array with last element as pivot int partition(int arr[], int low, int high) { int pivot = arr[high]; int i = (low-1); // index of smaller element for (int j=low; j Výkon:
Vstupné pole
ako zmeniť video z youtube na súbor wav
12 23 3 43 51 35 19 45
Pole po triedení pomocou rýchleho triedenia
3 12 19 23 35 43 45 51
Aj v implementácii Java sme použili rovnakú logiku, ktorú sme použili v implementácii C ++. Posledný prvok v poli sme použili ako otočný a na paneli sa vykonáva rýchle triedenie, aby sa otočný prvok umiestnil do správnej polohy.
Analýza zložitosti algoritmu Quicksort
Čas, ktorý quicksort vyžaduje na zoradenie poľa, závisí od stratégie alebo metódy vstupného poľa a oddielov.
Ak k je počet prvkov menší ako pivot a n je celkový počet prvkov, potom je možné všeobecný čas potrebný pre rýchle triedenie vyjadriť takto:
T (n) = T (k) + T (n-k-1) + O (n)
Tu sú T (k) a T (n-k-1) čas potrebný na rekurzívne volania a O (n) je čas potrebný na rozdelenie hovoru.
Poďme si podrobne analyzovať túto časovú zložitosť pre quicksort.
# 1) Najhorší prípad : Najhorší prípad v technike quicksort nastáva väčšinou vtedy, keď ako pivot vyberieme najnižší alebo najvyšší prvok v poli. (Na vyššie uvedenej ilustrácii sme ako pivot vybrali najvyšší prvok). V takejto situácii nastane najhorší prípad, keď je radené pole už zoradené vzostupne alebo zostupne.
Preto sa vyššie uvedený výraz pre celkový čas mení ako:
T (n) = T (0) + T (n-1) + O (n) ktoré sa rozhodnú pre O (ndva)
# 2) Najlepší prípad: Najlepší prípad pre rýchle triedenie nastane vždy, keď je vybraný otočný prvok v strede poľa.
Opakovanie v najlepšom prípade je teda:
T (n) = 2T (n / 2) + O (n) = O (nlogn)
bezplatný softvér na prevod videa pre Windows 10
# 3) Priemerný prípad: Na analýzu priemerného prípadu pre quicksort by sme mali vziať do úvahy všetky permutácie poľa a potom vypočítať čas potrebný každej z týchto permutácií. Stručne povedané, priemerný čas pre quicksort sa tiež stáva O (nlogn).
Ďalej uvádzame rôzne zložitosti techniky Quicksort:
Najhoršia časová zložitosť O (n 2) stabilita Nie sú stabilné, pretože dva prvky s rovnakými hodnotami nebudú umiestnené v rovnakom poradí. Stabilný - v zoradenom výstupe sa objavia dva prvky s rovnakými hodnotami v rovnakom poradí. Najlepšia časová zložitosť prípadu O (n * log n) Priemerná časová zložitosť O (n * log n) Zložitosť priestoru O (n * log n)
Quicksort môžeme implementovať mnohými rôznymi spôsobmi, stačí zmeniť výber otočného prvku (stredný, prvý alebo posledný), najhorší prípad sa však pre quicksort vyskytne zriedka.
3-smerný Quicksort
V pôvodnej technike rýchleho triedenia zvyčajne vyberieme otočný prvok a potom rozdelíme pole na čiastkové polia okolo tohto otočného bodu tak, aby jedno čiastkové pole pozostávalo z prvkov menších ako otočný čap a ďalšie pozostávalo z prvkov väčších ako otočný čap.
Čo však robiť, ak vyberieme otočný prvok a v poli je viac ako jeden prvok, ktorý sa rovná otočnému?
Napríklad, zvážte nasledujúce pole {5,76,23,65,4,4,5,4,1,1,2,2,2,2}. Ak na tomto poli vykonáme jednoduchý quicksort a ako otočný prvok vyberieme 4, potom opravíme iba jeden výskyt prvku 4 a zvyšok sa rozdelí na oddiely spolu s ostatnými prvkami.
Namiesto toho, ak použijeme 3-smerný quicksort, rozdelíme pole [l… r] do troch podradených polí takto:
- Array [l ... i] - Tu je i pivot a toto pole obsahuje prvky menšie ako pivot.
- Pole [i + 1… j-1] - obsahuje prvky, ktoré sa rovnajú bodu pivot.
- Pole [j… r] - obsahuje prvky väčšie ako pivot.
Teda trojcestný quicksort sa dá použiť, keď máme v poli viac ako jeden redundantný prvok.
Randomizovaný Quicksort
Technika quicksortu sa nazýva randomizovaná technika quicksortu, keď na výber prvku pivot používame náhodné čísla. V randomizovanom quicksortu sa to nazýva „centrálny pivot“ a rozdeľuje pole takým spôsobom, že každá strana má minimálne ¼ prvkov.
Pseudokód pre randomizovaný quicksort je uvedený nižšie:
// Sorts an array arr[low..high] using randomized quick sort randomQuickSort(array[], low, high) array – array to be sorted low – lowest element in array high – highest element in array begin 1. If low >= high, then EXIT. //select central pivot 2. While pivot 'pi' is not a Central Pivot. (i) Choose uniformly at random a number from [low..high]. Let pi be the randomly picked number. (ii) Count elements in array[low..high] that are smaller than array[pi]. Let this count be a_low. (iii) Count elements in array[low..high] that are greater than array[pi]. Let this count be a_high. (iv) Let n = (high-low+1). If a_low >= n/4 and a_high >= n/4, then pi is a central pivot. //partition the array 3. Partition array[low..high] around the pivot pi. 4. // sort first half randomQuickSort(array, low, a_low-1) 5. // sort second half randomQuickSort(array, high-a_high+1, high) end procedureVo vyššie uvedenom kóde „randomQuickSort“ v kroku č. 2 vyberieme centrálny pivot. V kroku 2 je pravdepodobnosť, že vybraný prvok bude stredovým čapom, je ½. Preto sa očakáva, že slučka v kroku 2 prebehne dvakrát. Časová zložitosť pre krok 2 v randomizovanom rýchlorezom je teda O (n).
Použitie slučky na výber centrálneho otočného čapu nie je ideálnym spôsobom na implementáciu náhodného rýchleho triedenia. Namiesto toho môžeme náhodne vybrať prvok a nazvať ho centrálnym otočným prvkom alebo zmeniť štruktúru prvkov poľa. Očakávaná najhoršia časová zložitosť pre randomizovaný algoritmus rýchleho triedenia je O (nlogn).
Quicksort vs. Merge Sort
V tejto časti rozoberieme hlavné rozdiely medzi rýchlym zoradením a zlúčením.
Parameter porovnania Rýchle triedenie Zlúčiť triedenie rozdelenie Pole je rozdelené okolo otočného prvku a nemusí byť vždy vždy rozdelené na dve polovice. Môže byť rozdelený v ľubovoľnom pomere. Pole je rozdelené na dve polovice (n / 2). Najhoršia zložitosť prípadu O (n 2) - v najhoršom prípade sa vyžaduje veľa porovnaní. O (nlogn) - rovnaké ako priemerný prípad Využitie množín údajov S väčšími množinami údajov nefunguje dobre. Funguje dobre so všetkými súbormi údajov bez ohľadu na veľkosť. Dodatočný priestor Na mieste - nepotrebuje ďalší priestor. Nie je na mieste - potrebuje ďalší priestor na uloženie pomocného poľa. Metóda triedenia Interné - dáta sú zoradené v hlavnej pamäti. Externé - používa externú pamäť na ukladanie dátových polí. Účinnosť Rýchlejšie a efektívnejšie pre malé zoznamy. Rýchle a efektívne pre väčšie zoznamy. Polia / prepojené zoznamy Výhodnejšie pre polia. Funguje dobre pre prepojené zoznamy.
Záver
Ako už názov napovedá, quicksort je algoritmus, ktorý triedi zoznam rýchlo ako všetky ostatné algoritmy triedenia. Rovnako ako zlúčenie, rýchle triedenie tiež využíva stratégiu rozdelenia a dobývania.
Ako sme už videli, pomocou rýchleho triedenia rozdelíme zoznam na podradné polia pomocou prvku pivot. Potom sú tieto čiastkové polia nezávisle zoradené. Na konci algoritmu je celé pole úplne zoradené.
Quicksort je rýchlejší a efektívne pracuje na triedení dátových štruktúr. Quicksort je populárny algoritmus triedenia a niekedy je dokonca uprednostňovaný pred algoritmom zlúčenia.
V našom ďalšom výučbe sa budeme podrobnejšie zaoberať triedením Shell.
=> Dajte si pozor na jednoduchú sériu školení C ++ tu.
Odporúčané čítanie
- Metóda MongoDB Sort () s príkladmi
- Unixový príkaz na triedenie so syntaxou, možnosťami a príkladmi
- Zlúčiť zoradenie v C ++ s príkladmi
- Hromadné triedenie v C ++ s príkladmi
- Shell zoradený v C ++ s príkladmi
- Výber Zoradiť v C ++ s príkladmi
- Bublinové triedenie v C ++ s príkladmi
- Zoradenie vloženia v C ++ s príkladmi
