Tutto quello che devi sapere su Quicksort in C ++

Ci sono una miriade di algoritmi di ordinamento. Trovare la misura giusta per la tua applicazione è un'attività che richiede una breve comprensione di fattori quali prestazioni, complessità temporale, lunghezza del codice, ecc. Di un particolare algoritmo. In questo post, daremo uno sguardo a tutti i concetti essenziali richiesti per implementare il Quicksort in C ++ nel seguente ordine:

• Comprensione dell'algoritmo Quicksort
• Pseudocodice per Quicksort
• Programma di Quicksort in C ++
• Time Complexity Quicksort

Comprensione dell'algoritmo Quicksort

Proprio come Unisci ordinamento , Quicksort segue la strategia divide et impera. Utilizzando la strategia divide et impera, dividiamo il problema in molti sottoproblemi e li risolviamo in modo ricorsivo. In primo luogo, comprenderemo l'intero processo passo dopo passo e successivamente, con l'aiuto di un esempio, svilupperemo una profonda comprensione dell'intero processo.

1. Per prima cosa, chiederemo all'utente l'array non ordinato.

2. Una volta che abbiamo il nostro array non ordinato, dobbiamo selezionare un valore pivot dall'array. Possiamo scegliere qualsiasi valore.

   
   
   

3. Dopo aver selezionato il punto di pivot, dobbiamo disporre gli altri elementi dell'array in modo tale che tutti gli elementi inferiori al valore di pivot siano posizionati a destra del valore di pivot e tutti gli elementi maggiori del pivot il valore deve essere posizionato a destra del valore pivot.

4. Eseguiamo il passaggio 3 finché non otteniamo il nostro array ordinato.

Ora, consideriamo un esempio e implementiamo l'algoritmo e vediamo come funziona.

Salve [5, 4, 1, 11, 9, 6, 2, 3] per questo esempio considereremo sempre il pivot come l'elemento più a destra della lista.

Esaminiamo ogni passaggio e comprendiamo la logica che abbiamo utilizzato per risolvere il problema.

• Innanzitutto, abbiamo selezionato '3' come perno e disposto tutti gli elementi minori di '3' a destra e tutti gli elementi maggiori di '3' a destra.

• A questo punto, abbiamo 2 sottoproblemi. Per prima cosa risolviamo il problema secondario a destra. Ne abbiamo selezionato uno come perno e abbiamo posizionato '2' a destra.

• Per risolvere il secondo sottoproblema selezioniamo '6' come nostro perno e posizioniamo gli elementi come discusso in precedenza.

• Abbiamo altri 2 sottoproblemi. Il primo si risolve selezionando 4 come pivot e il secondo si risolve selezionando 9 come pivot. Infine, abbiamo il nostro array ordinato con gli elementi posizionati nell'indice di sottolineatura.

  come usare la classe scanner in java

Nota- Il punto importante da capire qui è che tutte le operazioni avvengono nello stesso array. Non vengono creati nuovi array.

Pseudocodice per Quicksort in C ++

QuickSort (array [], start_index, end_index) {if (start_index
 Programma di Quicksort in C ++ 
Abbiamo compreso l'algoritmo e sviluppato una profonda comprensione del funzionamento dell'algoritmo. Implementiamo Quicksort in C ++ e scriviamo un programma per ordinare un array.
#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 = array [end_index] int i = (start_index - 1) per (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<>Costo numero di elementi<<'Enter the elements one by one: ' for(i=0i>Ciao [i]} quickSort (Hello, 0, NumberofElements-1) printArray (Hello, NumberofElements) return 0}
 Produzione: 
 Complessità temporale 
Parliamo dell'aspetto più importante di qualsiasi algoritmo di ordinamento, ovvero la complessità del tempo. Ci parla delle prestazioni dell'algoritmo in vari scenari. Questi valori possono aiutarci a decidere se possiamo utilizzare questo algoritmo per la nostra applicazione.
 Caso migliore- Su)
 Caso medio (nlogn)
 Nel peggiore dei casi Su2)
Con questo, arriviamo alla fine di questo articolo di Quicksort in C ++. Se desideri saperne di più, dai un'occhiata al   da Edureka, una società di apprendimento online affidabile. Il corso di formazione e certificazione Java J2EE e SOA di Edureka è progettato per formarti sia sui concetti di base che avanzati su Java insieme a vari framework Java come Hibernate e Spring.
 Hai domande per noi? Per favore, menzionalo nella sezione commenti di questo blog e ti risponderemo il prima possibile.