Lordinamento rapido è un algoritmo di ordinamento altamente efficiente e si basa sul partizionamento di array di dati in array più piccoli. Un array di grandi dimensioni è partizionato in due array, uno dei quali contiene valori inferiori al valore specificato, ad esempio pivot, in base al quale viene creata la partizione e un altro array contiene valori maggiori del valore pivot.
Partizioni Quicksort un array e quindi chiama se stesso ricorsivamente due volte per ordinare i due sottoarray risultanti. Questo algoritmo è abbastanza efficiente per set di dati di grandi dimensioni poiché la sua complessità media e nel caso peggiore sono rispettivamente O (n2).
Partizione in ordinamento rapido
La seguente rappresentazione animata spiega come per trovare il valore pivot in un array.
Il valore pivot divide lelenco in due parti. E ricorsivamente, troviamo il pivot per ogni sottoelenco finché tutti gli elenchi non contengono un solo elemento.
Algoritmo pivot di ordinamento rapido
In base alla nostra comprensione del partizionamento in ordinamento rapido, lo faremo ora prova a scrivere un algoritmo per esso, che è il seguente.
Step 1 − Choose the highest index value has pivotStep 2 − Take two variables to point left and right of the list excluding pivotStep 3 − left points to the low indexStep 4 − right points to the highStep 5 − while value at left is less than pivot move rightStep 6 − while value at right is greater than pivot move leftStep 7 − if both step 5 and step 6 does not match swap left and rightStep 8 − if left ≥ right, the point where they met is new pivot
Pseudocodice pivot di ordinamento rapido
Lo pseudocodice per lalgoritmo precedente può essere derivato come –
Algoritmo di ordinamento rapido
Usando lalgoritmo pivot in modo ricorsivo, si finisce con partizioni più piccole possibili. Ogni partizione viene quindi elaborata per lordinamento rapido. Definiamo lalgoritmo ricorsivo per quicksort come segue:
Step 1 − Make the right-most index value pivotStep 2 − partition the array using pivot valueStep 3 − quicksort left partition recursivelyStep 4 − quicksort right partition recursively
Pseudocodice di ordinamento rapido
Per approfondire, vediamo lo pseudocodice per algoritmo di ordinamento –
Per conoscere limplementazione rapida dellordinamento nel linguaggio di programmazione C, fare clic qui.