Ordinamento rapido in c ++

Organizzare le cose in sequenza è un compito che eseguiamo nella vita quotidiana, sia che sia organizzato in ordine crescente o in ordine decrescente. Il processo di organizzazione delle cose in una sequenza corretta si chiama smistamento. Ascendente sta aumentando l'ordine e la discendenza sta diminuendo l'ordine. Nella programmazione, eseguiamo anche l'ordinamento usando diversi algoritmi. Ma un algoritmo fornisce il più rapido smistamento che è "ordinamento rapido". Questo algoritmo di smistamento ordina l'array più velocemente degli altri algoritmi. Funziona sulla regola della divisione e conquista, imposta per primo un punto di perno e divide l'array in due sotto-array. Quindi, impostare un perno per i sotto-array e il processo continua fino a raggiungere la fine e l'array richiesto viene ordinato. Questo articolo spiega un lavoro approfondito di un rapido ordinamento in C ++ con un esempio di codifica pratica in ordine crescente.

Come selezionare un perno

Prima di passare a ulteriori dettagli, è importante imparare come possiamo selezionare un perno per l'algoritmo di ordinamento rapido.

• • Primo elemento
  • Ultimo elemento
  • Elemento mediano
  • Elemento casuale

Non ci sono restrizioni per la selezione di un perno. Principalmente, impostiamo l'ultimo valore dell'array come punto di perno.

Algoritmi:

L'ordinamento rapido viene eseguito usando due algoritmi: uno è di partizionare l'array secondo il punto di pivot e l'altro è per ordinare l'array.

Per il partizionamento:

• • Prendi due variabili come il più basso e il più alto.
  • Conservare l'indice di partenza dell'array nel più basso e quindi conservare l'ultimo indice in quello più alto.
  • Definisci un'altra variabile e inizializzala con la variabile più bassa come "ITER".
  • Seleziona l'ultimo membro dell'array per agire come perno.
  • Passare attraverso l'array. Successivamente, abbina ogni elemento con il valore del perno.
  • Se l'elemento array è inferiore al perno, incrementa il "iter" e scambia le loro posizioni.
  • Incrementare "i" per 1 e ripetere il processo fino a raggiungere l'estremità dell'array. Termina il loop lì e restituisce ITER-1.

Il valore restituito ci dà la posizione dell'indice per pivot. Prima del perno, ci sono gli elementi più piccoli del valore per il perno. Dopo il perno, ci sono gli elementi che sono maggiori del valore per giro.

Per l'ordinamento:

Ora, passa all'ordinamento. Usa le seguenti istruzioni per ordinare un array:

• • Scegli l'ultimo elemento dell'array per agire come perno.
  • L'algoritmo di partizione dell'indice restituito è l'indice corretto di un perno.
  • Il metodo QuickSort viene chiamato ripetutamente sui subarray sinistro e destro.

Con l'aiuto di questi due algoritmi, possiamo eseguire l'ordinamento rapido su qualsiasi array. Un esempio del metodo di ordinamento rapido è chiarito nel seguente:

Ordinamento rapido in ordine crescente

Spieghiamo il metodo "Ordine rapida" per ordinare un array intero in ordine crescente.

Codice:

#includere
Utilizzo dello spazio dei nomi std;
void swap (int array_0 [], int position_1, int position_2)
int temp_0;
temp_0 = array_0 [position_1];
array_0 [position_1] = array_0 [position_2];
array_0 [position_2] = temp_0;
int partizione (int array_0 [], int basso, int alto, int pivot)
int i_0 = basso;
int j_0 = basso;
while (I_0 <= high) if(array_0[i_0] > pivot) i_0 ++;
else swap (array_0, i_0, j_0); I_0 ++; J_0 ++;
restituire j_0-1;

void QuickSort_0 (int array_0 [], int basso, int alto)
Se (basso < high)
int pivot = array_0 [high];
int position = partizione (array_0, basso, alto, perno);
QuickSort_0 (Array_0, Low, Position-1);
QuickSort_0 (array_0, posizione+1, alto);
int main ()

int n [4] = 12,3,8,6;
QuickSort_0 (n, 0, 3);
cout<<"The sorted array is: ";
per (int i = 0; i < 4 ; i++) cout<< n[i]<<"\t";

Avvia il codice importando la libreria e includi lo spazio dei nomi standard. Successivamente, definisci un metodo chiamato "scambio" del tipo di ritorno void. In questa funzione, passa tre parametri con tipo intero. I due argomenti, "position_1" e "position_2", sono usati per le posizioni. Il terzo, "temp_0", è un array. Il metodo scambia le posizioni degli elementi dell'array. La variabile denominata "temp_0" è dichiarata per salvare temporaneamente il valore. Inoltre, inizializza questo "temp_0" con la prima posizione dell'array. Quindi, assegna la seconda posizione dell'array alla prima posizione di un array "position_1". E assegnare la temperatura alla seconda posizione dell'array che è "position_2". Funziona come a = b; b = c; c = a. Questo metodo esegue solo lo scambio.

Oltre a ciò, definisci un'altra funzione per la partizione. Questo metodo divide l'array in due parti e divide ulteriormente i sotto-array in sotto-array. Questa funzione è un metodo di tipo reso e restituisce un valore intero che contiene l'indice corretto del perno. Questo metodo di partizione () ha quattro argomenti di tipo intero. Il primo è un array di "array_0", il secondo è "basso" che memorizza l'indice iniziale dell'array, il terzo è "alto" che contiene l'ultimo indice dell'array, e il quarto è "perno". All'interno di questo metodo, inizializza due variabili - "I_0" e "J_0" - con "Low". Queste due variabili hanno un tipo di dati "int". Come sappiamo, "basso" contiene l'indice iniziale dell'array. Nella riga successiva, usa il ciclo "while" per iterare sull'array. Innanzitutto, imposta la condizione di "'while” come I_0 <= high. Iterate until we reach the last index of the array. Inside the “while” loop, employ the “if” decision-making statement to check whether the array elements are greater than the pivot or not. If this condition is fulfilled, the body of “if” executes which increments the iterator. Otherwise, the body of “else” is run. In the body of “else”, we callthe swap() method that swaps the array values until they are in ascending order. Outside the “while”, return the “j_0-1” to the function. Because that is incremented in the “else” part.

Definire un altro metodo QuickSort () di tipo di restituzione del vuoto per eseguire il rapido smistamento. Tre argomenti - "Array_0", "Low" e "High" - hanno un tipo di tipo intero a questa funzione. Inoltre, imposta la condizione "if". Se "basso" è inferiore al "alto", inizializza il "perno" con l'ultimo indice dell'array "alto". Per la variabile "posizione", chiamare il metodo di partizione (). Quindi, invoca ricorsivamente la funzione QuickSort () sui sotto-array destro e sinistro.

Nell'ultima parte del codice, impiega il metodo principale (). Quindi, inizializza un array di tipo "int" e chiama il metodo QuickSort_0 (). Questa funzione contiene tre argomenti. Esegue un rapido ordinamento sull'array specificato e ordina questo array. Inserisci il "cout<<” command to print the “The sorted array is:” line. To display the sorted array, use a “for” loop and iterate until the end of the array is reached.

Produzione:

L'array ordinato è: 3 6 8 12

Conclusione

L'ordinamento rapido in C ++ è discusso in questa guida. Nella programmazione, è necessario disporre gli array in ordine crescente o discendente. Esistono più algoritmi di smistamento come la bolle, unione, ecc. Sort Sort è uno di questi, ma come dice il nome, ordina l'array più rapidamente di altri. Questo articolo spiega cos'è un perno, quale elemento di array può essere il perno, quali algoritmi vengono utilizzati per l'ordinamento rapido e come si esibiscono. Questo articolo si conclude con il codice di C ++ in cui implementiamo l'ordinamento rapido.