quick sort c with examples
Quicksort în C ++ cu ilustrație.
Quicksort este un algoritm de sortare utilizat pe scară largă, care selectează un element specific numit „pivot” și partiționează matricea sau lista pentru a fi sortate în două părți pe baza acestui pivot s0 că elementele mai mici decât pivotul sunt la stânga listei și elementele mai mari decât pivotul se află în dreapta listei.
Astfel, lista este împărțită în două subliste. Este posibil ca sublistele să nu fie necesare pentru aceeași dimensiune. Apoi Quicksort se numește recursiv pentru a sorta aceste două subliste.
=> Consultați aici ghidul perfect de formare C ++.
Ce veți învăța:
- Introducere
- Algoritm general
- Pseudo Cod pentru Quicksort
- Ilustrare
- Exemplu C ++
- Exemplu Java
- Analiza complexității algoritmului Quicksort
- Quicksort cu 3 căi
- Quicksort aleatoriu
- Quicksort vs. Merge Sort
- Concluzie
- Lectură recomandată
Introducere
Quicksort funcționează eficient și mai rapid, chiar și pentru tablouri sau liste mai mari.
În acest tutorial, vom explora mai multe despre funcționarea Quicksort împreună cu câteva exemple de programare a algoritmului quicksort.
Ca valoare pivot, putem alege fie prima, ultima sau valoarea medie sau orice valoare aleatorie. Ideea generală este că, în cele din urmă, valoarea pivotului este plasată la poziția corectă în matrice, deplasând celelalte elemente din matrice la stânga sau la dreapta.
Algoritm general
Algoritmul general pentru Quicksort este dat mai jos.
quicksort(A, low, high) begin Declare array A(N) to be sorted low = 1st element; high = last element; pivot if(low Să aruncăm o privire asupra pseudocodului pentru tehnica Quicksort.
Pseudo Cod pentru 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 Funcționarea algoritmului de partiționare este descrisă mai jos folosind un exemplu.
În această ilustrație, luăm ultimul element ca pivot. Putem vedea că matricea este împărțită succesiv în jurul elementului pivot până când avem un singur element în matrice.
Acum prezentăm o ilustrare a Quicksortului de mai jos pentru a înțelege mai bine conceptul.
Ilustrare
Să vedem o ilustrare a algoritmului rapid. Luați în considerare următoarea matrice cu ultimul element ca pivot. De asemenea, primul element este etichetat scăzut, iar ultimul element este ridicat.
diferența dintre declanșarea portului și redirecționarea portului
Din ilustrație, putem vedea că mutăm pointerele în sus și în jos la ambele capete ale matricei. Ori de câte ori punctele joase către elementul mai mare decât pivotul și punctele înalte către elementul mai mic decât pivotul, atunci schimbăm pozițiile acestor elemente și avansăm indicatoarele joase și înalte în direcțiile lor respective.
Acest lucru se face până când indicatoarele joasă și înaltă se încrucișează. Odată ce se încrucișează, elementul pivot este plasat în poziția corectă și matricea este partiționată în două. Apoi, ambele sub-tablouri sunt sortate independent folosind quicksort recursiv.
Exemplu C ++
Mai jos este implementarea algoritmului Quicksort în 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< Ieșire:
Matrice de intrare
12 23 3 43 51 35 19 45
Tablou sortat cu rapid rapid
3 12 19 23 35 43 45 51
Aici avem câteva rutine care sunt folosite pentru partiționarea matricei și apelarea quicksort recursiv pentru a sorta partiția, funcția de bază quicksort și funcțiile utilitare pentru a afișa conținutul matricei și a schimba cele două elemente în consecință.
În primul rând, numim funcția quicksort cu matricea de intrare. În interiorul funcției Quicksort, numim funcția de partiție. În funcția de partiție, folosim ultimul element ca element pivot pentru matrice. Odată ce pivotul este decis, matricea este partiționată în două părți și apoi funcția quicksort este apelată pentru a sorta independent ambele matrice.
Când se întoarce funcția quicksort, matricea este sortată astfel încât elementul pivot să fie la locația corectă și elementele mai mici decât pivotul să fie în stânga pivotului și elementele mai mari decât pivotul să fie în dreapta pivotului.
aplicație web document de plan de testare
Apoi, vom implementa algoritmul quicksort în Java.
Exemplu 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 Ieșire:
Matrice de intrare
12 23 3 43 51 35 19 45
Matrice după sortare cu rapid rapid
3 12 19 23 35 43 45 51
Și în implementarea Java, am folosit aceeași logică pe care am folosit-o în implementarea C ++. Am folosit ultimul element din matrice, deoarece pivotul și quicksort sunt efectuate pe matrice pentru a plasa elementul pivot în poziția corectă.
Analiza complexității algoritmului Quicksort
Timpul luat de quicksort pentru a sorta o matrice depinde de matricea de intrare și de strategia sau metoda partiției.
Dacă k este numărul de elemente mai mic decât pivotul și n este numărul total de elemente, atunci timpul general luat de quicksort poate fi exprimat după cum urmează:
T (n) = T (k) + T (n-k-1) + O (n)
Aici, T (k) și T (n-k-1) sunt timpul necesar apelurilor recursive și O (n) este timpul luat de apelul de partiționare.
Să analizăm în detaliu această complexitate a timpului pentru rapiditatea rapidă.
# 1) Cel mai rău caz : Cel mai rău caz în tehnica quicksort apare mai ales atunci când selectăm cel mai mic sau cel mai înalt element din matrice ca pivot. (În ilustrația de mai sus am selectat cel mai înalt element ca pivot). Într-o astfel de situație, cel mai rău caz apare atunci când matricea care trebuie sortată este deja sortată în ordine crescătoare sau descendentă.
Prin urmare, expresia de mai sus pentru timpul total luat se modifică ca:
T (n) = T (0) + T (n-1) + O (n) care se rezolvă la PeDouă)
# 2) Cel mai bun caz: Cel mai bun caz pentru quicksort apare întotdeauna când elementul pivot selectat este mijlocul matricei.
Astfel, recurența pentru cel mai bun caz este:
diferența dintre testarea sarcinii și testarea performanței
T (n) = 2T (n / 2) + O (n) = O (nlogn)
# 3) Caz mediu: Pentru a analiza cazul mediu pentru quicksort, ar trebui să luăm în considerare toate permutările matricei și apoi să calculăm timpul luat de fiecare dintre aceste permutări. Pe scurt, timpul mediu pentru rapidul rapid devine și O (nlogn).
Mai jos sunt prezentate diferitele complexități pentru tehnica Quicksort:
Complexitatea timpului cel mai prost O (n 2) stabilitate Nu este stabil, deoarece două elemente cu aceleași valori nu vor fi plasate în aceeași ordine. Stabil - două elemente cu aceleași valori vor apărea în aceeași ordine în ieșirea sortată. Complexitatea în cel mai bun caz O (n * jurnal n) Complexitatea medie a timpului O (n * jurnal n) Complexitatea spațiului O (n * jurnal n)
Putem implementa quicksort în multe moduri diferite doar schimbând alegerea elementului pivot (mijloc, primul sau ultimul), cu toate acestea, cel mai rău caz apare rar pentru quicksort.
Quicksort cu 3 căi
În tehnica quicksort originală, de obicei selectăm un element de pivotare și apoi împărțim matricea în sub-tablouri din jurul acestui pivot, astfel încât un sub-tablou să fie format din elemente mai mici decât pivotul și altul constă din elemente mai mari decât pivotul.
Dar dacă selectăm un element pivot și există mai multe elemente în matrice care este egal cu pivot?
De exemplu, ia în considerare următoarea matrice {5,76,23,65,4,4,5,4,1,1,2,2,2,2}. Dacă executăm un simplu quicksort pe această matrice și selectăm 4 ca element pivot, atunci vom remedia o singură apariție a elementului 4, iar restul va fi partiționat împreună cu celelalte elemente.
În schimb, dacă folosim quicksort cu 3 căi, atunci vom împărți matricea (l ... r) în trei sub-tablouri după cum urmează:
- Matrice (l ... i) - Aici, i este pivotul și acest tablou conține elemente mai mici decât pivotul.
- Matrice (i + 1 ... j-1) - Conține elementele care sunt egale cu pivotul.
- Array (j ... r) - Conține elemente mai mari decât pivotul.
Astfel, rapidul cu 3 căi poate fi utilizat atunci când avem mai multe elemente redundante în matrice.
Quicksort aleatoriu
Tehnica quicksort se numește tehnică quicksort randomizată atunci când folosim numere aleatorii pentru a selecta elementul pivot. În quicksort aleatoriu, se numește „pivot central” și împarte matricea în așa fel încât fiecare parte să aibă cel puțin ¼ elemente.
Pseudo-codul pentru rapidul randomizat este dat mai jos:
// 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 procedureÎn codul de mai sus de pe „randomQuickSort”, la pasul 2 selectăm pivotul central. La pasul 2, probabilitatea ca elementul selectat să fie pivotul central este ½. Prin urmare, bucla din pasul 2 este de așteptat să ruleze de 2 ori. Astfel, complexitatea timpului pentru pasul 2 în rapidul randomizat este O (n).
Folosirea unei bucle pentru a selecta pivotul central nu este modalitatea ideală de a implementa rapidul randomizat. În schimb, putem selecta aleatoriu un element și îl putem numi pivot central sau remodela elementele matricei. Complexitatea în cel mai rău caz așteptat pentru algoritmul rapid rapid aleatorizat este O (nlogn).
Quicksort vs. Merge Sort
În această secțiune, vom discuta despre principalele diferențe dintre sortarea rapidă și sortarea Merge.
Parametru de comparație Sortare rapida Merge sort partiționare Matricea este partiționată în jurul unui element pivot și nu este neapărat întotdeauna în două jumătăți. Poate fi partiționat în orice raport. Matricea este partiționată în două jumătăți (n / 2). Complexitatea celui mai prost caz O (n 2) - sunt necesare multe comparații în cel mai rău caz. O (nlogn) - la fel ca în cazul mediu Utilizarea seturilor de date Nu pot funcționa bine cu seturi de date mai mari. Funcționează bine cu toate seturile de date, indiferent de dimensiune. Spațiu suplimentar În loc - nu are nevoie de spațiu suplimentar. Nu este în loc - are nevoie de spațiu suplimentar pentru a stoca matricea auxiliară. Metoda de sortare Intern - datele sunt sortate în memoria principală. Extern - utilizează memorie externă pentru stocarea matricelor de date. Eficienţă Mai rapid și eficient pentru listele de dimensiuni mici. Rapid și eficient pentru liste mai mari. Matrice / liste legate Mai preferat pentru tablouri. Funcționează bine pentru listele conectate.
Concluzie
După cum sugerează și numele, quicksort este algoritmul care sortează lista rapid decât orice alt algoritm de sortare. La fel ca sortarea fuzionată, sortarea rapidă adoptă și o strategie de divizare și cucerire.
După cum am văzut deja, folosind sortarea rapidă împărțim lista în sub-tablouri folosind elementul pivot. Apoi, aceste sub-tablouri sunt sortate independent. La sfârșitul algoritmului, întreaga matrice este complet sortată.
Quicksort este mai rapid și funcționează eficient pentru sortarea structurilor de date. Quicksort este un algoritm de sortare popular și uneori este chiar preferat în comparație cu algoritmul de sortare a fuzionării.
În următorul nostru tutorial, vom discuta mai multe detalii despre sortarea Shell.
=> Urmăriți aici seria de antrenament C ++ simplă.
Lectură recomandată
- Metoda MongoDB Sort () cu exemple
- Comanda de sortare Unix cu sintaxă, opțiuni și exemple
- Merge Sortează în C ++ cu exemple
- Sortare în grămadă în C ++ cu exemple
- Sortare Shell în C ++ cu exemple
- Selecție Sortare în C ++ cu exemple
- Sortare cu bule în C ++ cu exemple
- Inserare Sortare în C ++ cu exemple
