quick sort c with examples
Quicksort en C ++ amb il·lustració.
Quicksort és un algorisme d'ordenació àmpliament utilitzat que selecciona un element específic anomenat 'pivot' i particiona la matriu o la llista per ordenar-la en dues parts basant-se en aquest pivot s0 que els elements menors que el pivot es troben a l'esquerra de la llista i els elements més gran que el pivot a la dreta de la llista.
Així, la llista es divideix en dues sublistes. És possible que les sublistes no siguin necessàries per a la mateixa mida. A continuació, Quicksort es diu recursivament per ordenar aquestes dues llistes.
=> Consulteu aquí la guia d’entrenament perfecta de C ++.
Què aprendreu:
- Introducció
- Algorisme general
- Codi pseudo per a Quicksort
- Il·lustració
- Exemple C ++
- Exemple de Java
- Anàlisi de complexitat de l'algorisme Quicksort
- Quicksort de 3 vies
- Quicksort aleatoritzat
- Quicksort vs. Merge Sort
- Conclusió
- Lectura recomanada
Introducció
Quicksort funciona de manera eficient i més ràpida, fins i tot per a matrius o llistes més grans.
En aquest tutorial, explorarem més sobre el funcionament de Quicksort juntament amb alguns exemples de programació de l'algorisme de quicksort.
Com a valor pivot, podem triar el primer, l’últim o el valor mitjà o qualsevol valor aleatori. La idea general és que, en última instància, el valor de pivot es col·loca a la seva posició correcta a la matriu movent els altres elements de la matriu cap a l'esquerra o cap a la dreta.
Algorisme general
A continuació es mostra l’algorisme general de Quicksort.
quicksort(A, low, high) begin Declare array A(N) to be sorted low = 1st element; high = last element; pivot if(low Vegem ara el pseudocodi de la tècnica Quicksort.
Codi pseudo per a 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 A continuació es descriu el funcionament de l'algorisme de particionament mitjançant un exemple.
En aquesta il·lustració, prenem l’últim element com a pivot. Podem veure que la matriu es divideix successivament al voltant de l’element pivot fins que tenim un únic element a la matriu.
Ara presentem una il·lustració del Quicksort a continuació per entendre millor el concepte.
Il·lustració
Vegem una il·lustració de l'algorisme de ràpida velocitat. Considereu la matriu següent amb l’últim element com a pivot. A més, el primer element s’etiqueta baix i l’últim element és alt.
quina diferència hi ha entre garantia de qualitat i control de qualitat
A la il·lustració, podem veure que movem els punteres cap amunt i cap avall als dos extrems de la matriu. Sempre que els punts baixos a l’element superiors al pivot i els punts alts a l’element menor que el pivot, intercanviem les posicions d’aquests elements i avançem els indicadors baix i alt en les seves respectives direccions.
Això es fa fins que els indicadors baix i alt es creuen. Un cop es creuen, l'element pivot es col·loca a la seva posició correcta i la matriu es divideix en dos. A continuació, aquestes dues sub-matrius s’ordenen de forma independent mitjançant quicksort recursivament.
Exemple C ++
A continuació es mostra la implementació de l'algorisme Quicksort en 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< Sortida:
Matriu d’entrada
12 23 3 43 51 35 19 45
Matriu classificada amb ràpid
3 12 19 23 35 43 45 51
Aquí tenim poques rutines que s’utilitzen per particionar la matriu i trucar a quicksort recursivament per ordenar la partició, la funció bàsica de quicksort i les funcions d’utilitat per mostrar el contingut de la matriu i intercanviar els dos elements en conseqüència.
En primer lloc, anomenem la funció quicksort amb la matriu d’entrada. Dins de la funció quicksort, anomenem la funció de partició. A la funció de partició, fem servir l'últim element com a element pivot de la matriu. Un cop decidit el pivot, la matriu es particiona en dues parts i, a continuació, es crida a la funció quicksort per ordenar independentment les matrius secundàries.
Quan torna la funció quicksort, la matriu s’ordena de manera que l’element pivot es troba a la seva ubicació correcta i els elements menors que el pivot es troben a l’esquerra del pivot i els elements més grans que el pivot es troben a la dreta del pivot.
A continuació, implementarem l'algorisme quicksort a Java.
Exemple de 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 Sortida:
Matriu d’entrada
12 23 3 43 51 35 19 45
Matriu després d’ordenar-les amb quicksort
3 12 19 23 35 43 45 51
També en la implementació de Java, hem utilitzat la mateixa lògica que la que vam fer en la implementació de C ++. Hem utilitzat l'últim element de la matriu ja que el pivot i el quicksort es realitzen a la matriu per tal de situar l'element pivot a la seva posició correcta.
Anàlisi de complexitat de l'algorisme Quicksort
El temps que triga Quicksort a ordenar una matriu depèn de la matriu d'entrada i l'estratègia o mètode de partició.
Si k és el nombre d'elements inferior al pivot i n és el nombre total d'elements, el temps general que pren el quicksort es pot expressar de la següent manera:
T (n) = T (k) + T (n-k-1) + O (n)
Aquí, T (k) i T (n-k-1) són el temps que prenen les trucades recursives i O (n) és el temps que prenen les trucades de partició.
Analitzem amb detall aquesta complexitat horària per obtenir una velocitat ràpida.
com fer un compte de correu electrònic fals
# 1) El pitjor cas : El pitjor cas de la tècnica de ràpida breu es produeix sobretot quan seleccionem l'element més baix o més alt de la matriu com a pivot. (A la il·lustració anterior hem seleccionat l'element més alt com a pivot). En aquesta situació, el pitjor dels casos es produeix quan la matriu a ordenar ja està ordenada en ordre ascendent o descendent.
Per tant, l’expressió anterior per al temps total que es pren canvia com:
T (n) = T (0) + T (n-1) + O (n) que es resol a O (n2)
# 2) El millor cas: El millor cas per a quicksort sempre es produeix quan l'element pivot seleccionat és el centre de la matriu.
Per tant, la recurrència del millor cas és:
com inicialitzar la variable estàtica en c ++
T (n) = 2T (n / 2) + O (n) = O (nlogn)
# 3) Cas mitjà: Per analitzar el cas mitjà de quicksort, hauríem de considerar totes les permutacions de matriu i després calcular el temps que triguen cadascuna d’aquestes permutacions. En poques paraules, el temps mitjà de ràpida breu també es converteix en O (nlogn).
A continuació es detallen les diverses complexitats de la tècnica Quicksort:
La pitjor complexitat temporal del cas O (n 2) estabilitat No és estable, ja que dos elements amb els mateixos valors no es col·locaran en el mateix ordre. Estable: dos elements amb els mateixos valors apareixeran en el mateix ordre a la sortida ordenada. Complexitat en el millor dels casos O (n * registre n) Complexitat temporal mitjana O (n * registre n) Complexitat espacial O (n * registre n)
Podem implementar quicksort de moltes maneres diferents només canviant l’elecció de l’element pivot (mig, primer o darrer), però, el pitjor dels casos rarament es produeix per a quicksort.
Quicksort de 3 vies
En la tècnica de quicksort original, normalment seleccionem un element de pivot i després dividim la matriu en sub-matrius al voltant d’aquest pivot de manera que un sub-matriu estigui format per elements inferiors al pivot i un altre estigui format per elements més grans que el pivot.
Però, què passa si seleccionem un element pivot i hi ha més d’un element a la matriu que és igual a pivot?
Per exemple, tingueu en compte la següent matriu {5,76,23,65,4,4,5,4,1,1,2,2,2,2}. Si realitzem un simple quicksort en aquesta matriu i seleccionem 4 com a element pivot, només arreglarem una ocurrència de l’element 4 i la resta es particionarà juntament amb els altres elements.
En lloc d'això, si fem servir el short-short de tres vies, dividirem la matriu (l ... r) en tres sub-matrius de la següent manera:
- Array (l ... i) - Aquí, i és el pivot i aquest array conté elements inferiors al pivot.
- Matriu (i + 1 ... j-1): conté els elements que són iguals al pivot.
- Matriu (j ... r): conté elements superiors al pivot.
Així, es pot utilitzar el quicksort de 3 vies quan tenim més d'un element redundant a la matriu.
Quicksort aleatoritzat
La tècnica quicksort s’anomena tècnica quicksort aleatòria quan fem servir números aleatoris per seleccionar l’element pivot. En el quicksort aleatori, s’anomena “pivot central” i divideix la matriu de manera que cada costat tingui almenys ¼ elements.
A continuació es dóna el pseudocodi per a un quicksort aleatori:
// 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 procedureAl codi anterior de 'randomQuickSort', al pas # 2 seleccionem el pivot central. Al pas 2, la probabilitat que l'element seleccionat sigui el pivot central és ½. Per tant, s’espera que el bucle del pas 2 s’executi 2 vegades. Per tant, la complexitat del temps per al pas 2 en el quicksort aleatori és O (n).
L’ús d’un bucle per seleccionar el pivot central no és la manera ideal d’implementar quicksort aleatori. En lloc d’això, podem seleccionar un element a l’atzar i anomenar-lo pivot central o remodelar els elements de la matriu. La complexitat temporal pitjor prevista per a l'algorisme de quicksort aleatori és O (nlogn).
Quicksort vs. Merge Sort
En aquesta secció, analitzarem les principals diferències entre l’ordenació ràpida i la combinació.
Paràmetre de comparació Classificació ràpida Combina la classificació particionament La matriu està particionada al voltant d’un element pivot i no necessàriament sempre es divideix en dues meitats. Es pot particionar en qualsevol proporció. La matriu està particionada en dues meitats (n / 2). La pitjor complexitat de casos O (n 2): es requereixen moltes comparacions en el pitjor dels casos. O (nlogn): igual que el cas mitjà Ús de conjunts de dades No es pot funcionar bé amb conjunts de dades més grans. Funciona bé amb tots els conjunts de dades, independentment de la mida. Espai addicional Al lloc: no necessita espai addicional. No al seu lloc: necessita espai addicional per emmagatzemar la matriu auxiliar. Mètode d'ordenació Intern: les dades s’ordenen a la memòria principal. Externa: utilitza memòria externa per emmagatzemar matrius de dades. Eficiència Més ràpid i eficaç per a llistes de mida petita. Ràpid i eficient per a llistes més grans. Matrius / llistes enllaçades Més preferit per a matrius. Funciona bé per a llistes enllaçades.
Conclusió
Com el seu propi nom indica, quicksort és l'algorisme que ordena la llista ràpidament que qualsevol altre algorisme d'ordenació. Igual que la classificació per fusió, la classificació ràpida també adopta una estratègia de divisió i conquesta.
Com ja hem vist, mitjançant l'ordenació ràpida dividim la llista en sub-matrius mitjançant l'element pivot. A continuació, aquestes sub-matrius s’ordenen independentment. Al final de l'algorisme, tota la matriu està completament ordenada.
Quicksort és més ràpid i funciona de manera eficient per ordenar les estructures de dades. Quicksort és un algorisme d'ordenació popular i, de vegades, fins i tot es prefereix a l'algorisme d'ordenació de combinació.
En el nostre proper tutorial, parlarem més detalladament sobre la classe Shell.
=> Mireu aquí la sèrie d'entrenament C ++ simple.
Lectura recomanada
- MongoDB Sort () Mètode amb exemples
- Ordre d'ordenació Unix amb sintaxi, opcions i exemples
- Combina l’ordenació en C ++ amb exemples
- Ordena en pila en C ++ amb exemples
- Ordenació de shell en C ++ amb exemples
- Selecció Ordena en C ++ amb exemples
- Classificació de bombolles en C ++ amb exemples
- Ordre d'inserció a C ++ amb exemples
