quick sort c with examples
Quicksort in C ++ con illustrazione.
Quicksort è un algoritmo di ordinamento ampiamente utilizzato che seleziona un elemento specifico chiamato 'pivot' e partiziona l'array o l'elenco da ordinare in due parti in base a questo pivot s0 che gli elementi minori del pivot si trovano a sinistra dell'elenco e degli elementi maggiore del perno si trovano a destra dell'elenco.
Pertanto l'elenco viene suddiviso in due sottoliste. Le sottoliste potrebbero non essere necessarie per la stessa dimensione. Quindi Quicksort chiama se stesso in modo ricorsivo per ordinare queste due sottoliste.
=> Dai un'occhiata alla guida di formazione C ++ perfetta qui.
Cosa imparerai:
- introduzione
- Algoritmo generale
- Pseudo codice per Quicksort
- Illustrazione
- Esempio C ++
- Esempio Java
- Analisi della complessità dell'algoritmo Quicksort
- Quicksort a 3 vie
- Quicksort randomizzato
- Quicksort vs. Merge Sort
- Conclusione
- Lettura consigliata
introduzione
Quicksort funziona in modo efficiente e più veloce anche per array o elenchi più grandi.
In questo tutorial, esploreremo di più sul funzionamento di Quicksort insieme ad alcuni esempi di programmazione dell'algoritmo Quicksort.
Come valore pivot, possiamo scegliere il primo, l'ultimo o il valore medio o qualsiasi valore casuale. L'idea generale è che alla fine il valore pivot viene posizionato nella posizione corretta nell'array spostando gli altri elementi nell'array a sinistra oa destra.
Algoritmo generale
Di seguito viene fornito l'algoritmo generale per Quicksort.
quicksort(A, low, high) begin Declare array A(N) to be sorted low = 1st element; high = last element; pivot if(low Diamo ora uno sguardo allo pseudocodice per la tecnica Quicksort.
Pseudo codice per 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 Il funzionamento dell'algoritmo di partizionamento è descritto di seguito utilizzando un esempio.
In questa illustrazione, prendiamo l'ultimo elemento come perno. Possiamo vedere che l'array viene diviso successivamente attorno all'elemento pivot fino a quando non abbiamo un singolo elemento nell'array.
Ora presentiamo di seguito un'illustrazione del Quicksort per comprendere meglio il concetto.
Illustrazione
Vediamo un'illustrazione dell'algoritmo quicksort. Considera il seguente array con l'ultimo elemento come pivot. Inoltre, il primo elemento è etichettato come basso e l'ultimo elemento è alto.
domande dell'intervista del team leader basate su scenari
Dall'illustrazione, possiamo vedere che, spostiamo i puntatori in alto e in basso a entrambe le estremità della matrice. Ogni volta che punti bassi all'elemento maggiore del perno e punti alti all'elemento minore del perno, allora scambiamo le posizioni di questi elementi e facciamo avanzare i puntatori alto e basso nelle rispettive direzioni.
Questo viene fatto fino a quando i puntatori basso e alto si incrociano. Una volta che si incrociano, l'elemento pivot viene posizionato nella posizione corretta e l'array viene suddiviso in due. Quindi entrambi questi sotto-array vengono ordinati in modo indipendente utilizzando quicksort in modo ricorsivo.
Esempio C ++
Di seguito è riportata l'implementazione dell'algoritmo Quicksort in 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< Produzione:
Matrice di input
12 23 3 43 51 35 19 45
come faccio ad aprire un file xml
Array ordinato con quicksort
3 12 19 23 35 43 45 51
Qui abbiamo poche routine che vengono utilizzate per partizionare l'array e chiamare quicksort ricorsivamente per ordinare la partizione, la funzione quicksort di base e le funzioni di utilità per visualizzare il contenuto dell'array e scambiare i due elementi di conseguenza.
Per prima cosa, chiamiamo la funzione quicksort con l'array di input. All'interno della funzione quicksort, chiamiamo la funzione di partizione. Nella funzione di partizione, usiamo l'ultimo elemento come elemento pivot per l'array. Una volta deciso il pivot, l'array viene partizionato in due parti e quindi viene chiamata la funzione quicksort per ordinare in modo indipendente entrambi i sotto-array.
Quando la funzione quicksort ritorna, l'array viene ordinato in modo tale che l'elemento pivot si trovi nella sua posizione corretta e gli elementi minori del pivot siano a sinistra del pivot e gli elementi maggiori del pivot siano a destra del pivot.
Successivamente, implementeremo l'algoritmo quicksort in Java.
Esempio 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 Produzione:
Matrice di input
12 23 3 43 51 35 19 45
Array dopo l'ordinamento con quicksort
3 12 19 23 35 43 45 51
Anche nell'implementazione Java, abbiamo usato la stessa logica che abbiamo usato nell'implementazione C ++. Abbiamo utilizzato l'ultimo elemento dell'array in quanto il pivot e il quicksort vengono eseguiti sull'array per posizionare l'elemento pivot nella posizione corretta.
Analisi della complessità dell'algoritmo Quicksort
Il tempo impiegato da quicksort per ordinare un array dipende dall'array di input e dalla strategia o dal metodo di partizione.
Se k è il numero di elementi inferiore al pivot e n è il numero totale di elementi, il tempo generale impiegato da quicksort può essere espresso come segue:
T (n) = T (k) + T (n-k-1) + O (n)
Qui, T (k) e T (n-k-1) sono il tempo impiegato dalle chiamate ricorsive e O (n) è il tempo impiegato dalla chiamata di partizionamento.
Analizziamo in dettaglio questa complessità temporale per Quicksort.
# 1) Caso peggiore : Il caso peggiore nella tecnica quicksort si verifica principalmente quando selezioniamo l'elemento più basso o più alto dell'array come pivot. (Nell'illustrazione sopra abbiamo selezionato l'elemento più alto come perno). In una tale situazione il caso peggiore si verifica quando l'array da ordinare è già ordinato in ordine crescente o decrescente.
Quindi l'espressione sopra per il tempo totale impiegato cambia come:
T (n) = T (0) + T (n-1) + O (n) che si risolve in SuDue)
# 2) Caso migliore: Il caso migliore per Quicksort si verifica sempre quando l'elemento pivot selezionato è al centro della matrice.
Quindi la ricorrenza per il caso migliore è:
protezione malware in tempo reale gratuita 2017
T (n) = 2 T (n / 2) + O (n) = O (nlogn)
# 3) Caso medio: Per analizzare il caso medio per quicksort, dovremmo considerare tutte le permutazioni di array e quindi calcolare il tempo impiegato da ciascuna di queste permutazioni. In poche parole, anche il tempo medio per Quicksort diventa O (nlogn).
Di seguito sono riportate le varie complessità per la tecnica Quicksort:
Complessità temporale nel caso peggiore O (n 2) stabilità Non è stabile in quanto due elementi con gli stessi valori non verranno inseriti nello stesso ordine. Stabile: due elementi con gli stessi valori appariranno nello stesso ordine nell'output ordinato. Migliore complessità temporale del caso O (n * log n) Complessità temporale media O (n * log n) Complessità spaziale O (n * log n)
Possiamo implementare il quicksort in molti modi diversi semplicemente cambiando la scelta dell'elemento pivot (medio, primo o ultimo), tuttavia, il caso peggiore si verifica raramente per quicksort.
Quicksort a 3 vie
Nella tecnica Quicksort originale, di solito selezioniamo un elemento pivot e quindi dividiamo l'array in sotto-array attorno a questo pivot in modo che un sotto-array sia composto da elementi inferiori al pivot e un altro da elementi maggiori del pivot.
Ma cosa succede se selezioniamo un elemento pivot e nell'array è presente più di un elemento uguale a pivot?
Per esempio, considera il seguente array {5,76,23,65,4,4,5,4,1,1,2,2,2,2}. Se eseguiamo un semplice quicksort su questo array e selezioniamo 4 come elemento pivot, allora correggeremo solo un'occorrenza dell'elemento 4 e il resto verrà partizionato insieme agli altri elementi.
Invece, se usiamo quicksort a 3 vie, divideremo l'array (l ... r) in tre sotto-array come segue:
- Array (l… i) - Qui i è il pivot e questo array contiene elementi inferiori al pivot.
- Array (i + 1… j-1) - Contiene gli elementi uguali al pivot.
- Array (j… r) - Contiene elementi maggiori del pivot.
Quindi il quicksort a 3 vie può essere utilizzato quando abbiamo più di un elemento ridondante nell'array.
Quicksort randomizzato
La tecnica quicksort è chiamata tecnica quicksort randomizzata quando usiamo numeri casuali per selezionare l'elemento pivot. Nel quicksort randomizzato, è chiamato 'perno centrale' e divide la matrice in modo tale che ogni lato abbia almeno ¼ di elementi.
Di seguito viene fornito lo pseudo-codice per il quicksort randomizzato:
// 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 procedureNel codice sopra su 'randomQuickSort', nel passaggio # 2 selezioniamo il perno centrale. Nella fase 2, la probabilità che l'elemento selezionato sia il perno centrale è ½. Quindi il ciclo nel passaggio 2 dovrebbe essere eseguito 2 volte. Quindi la complessità temporale per la fase 2 in quicksort randomizzato è O (n).
L'uso di un ciclo per selezionare il perno centrale non è il modo ideale per implementare un quicksort casuale. Invece, possiamo selezionare casualmente un elemento e chiamarlo pivot centrale o rimescolare gli elementi dell'array. La complessità temporale prevista nel caso peggiore per l'algoritmo quicksort randomizzato è O (nlogn).
Quicksort vs. Merge Sort
In questa sezione, discuteremo le principali differenze tra Ordinamento rapido e Ordinamento unito.
Parametro di confronto Ordinamento veloce Unisci ordinamento partizionamento L'array è partizionato attorno a un elemento pivot e non è necessariamente sempre in due metà. Può essere partizionato in qualsiasi rapporto. La matrice è suddivisa in due metà (n / 2). Peggiore complessità del caso O (n 2) - nel peggiore dei casi sono necessari molti confronti. O (nlogn) - lo stesso del caso medio Utilizzo dei set di dati Non può funzionare bene con set di dati più grandi. Funziona bene con tutti i set di dati indipendentemente dalle dimensioni. Spazio aggiuntivo Sul posto: non necessita di spazio aggiuntivo. Non sul posto - richiede spazio aggiuntivo per memorizzare l'array ausiliario. Metodo di ordinamento Interno: i dati vengono ordinati nella memoria principale. Esterno: utilizza la memoria esterna per archiviare matrici di dati. Efficienza Più veloce ed efficiente per elenchi di piccole dimensioni. Veloce ed efficiente per elenchi più grandi. Array / elenchi collegati Più preferito per gli array. Funziona bene per gli elenchi collegati.
Conclusione
Come suggerisce il nome stesso, quicksort è l'algoritmo che ordina l'elenco rapidamente rispetto a qualsiasi altro algoritmo di ordinamento. Proprio come il merge sort, anche il quick sort adotta una strategia divide et impera.
Come abbiamo già visto, utilizzando l'ordinamento rapido dividiamo l'elenco in sotto-array utilizzando l'elemento pivot. Quindi questi sotto-array vengono ordinati in modo indipendente. Alla fine dell'algoritmo, l'intero array è completamente ordinato.
Quicksort è più veloce e funziona in modo efficiente per l'ordinamento delle strutture di dati. Quicksort è un algoritmo di ordinamento popolare e talvolta è persino preferito all'algoritmo di ordinamento di unione.
Nel nostro prossimo tutorial, discuteremo di più sull'ordinamento della shell in dettaglio.
=> Guarda qui la serie di formazione C ++ semplice.
Lettura consigliata
- Metodo MongoDB Sort () con esempi
- Comando di ordinamento Unix con sintassi, opzioni ed esempi
- Unisci ordinamento in C ++ con esempi
- Ordinamento heap in C ++ con esempi
- Ordinamento della shell in C ++ con esempi
- Ordinamento di selezione in C ++ con esempi
- Bubble Sort in C ++ con esempi
- Ordinamento di inserzione in C ++ con esempi
