Struttura dei dati e algoritmi - Ordinamento rapido
L'ordinamento 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.
Quicksort partiziona un array e quindi chiama se stesso in modo ricorsivo 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 (n 2 ).
Partizione in ordinamento rapido
La seguente rappresentazione animata spiega come trovare il valore pivot in un array.
Il valore pivot divide l'elenco in due parti. E ricorsivamente, troviamo il pivot per ogni sottoelenco fino a quando tutti gli elenchi contengono un solo elemento.
Algoritmo pivot di ordinamento rapido
Sulla base della nostra comprensione del partizionamento nell'ordinamento rapido, proveremo ora a scrivere un algoritmo per esso, che è il seguente.
Step 1 − Choose the highest index value has pivot
Step 2 − Take two variables to point left and right of the list excluding pivot
Step 3 − left points to the low index
Step 4 − right points to the high
Step 5 − while value at left is less than pivot move right
Step 6 − while value at right is greater than pivot move left
Step 7 − if both step 5 and step 6 does not match swap left and right
Step 8 − if left ≥ right, the point where they met is new pivot
Pseudocodice pivot di ordinamento rapido
Lo pseudocodice per l'algoritmo di cui sopra può essere derivato come -
function partitionFunc(left, right, pivot)
leftPointer = left
rightPointer = right - 1
while True do
while A[++leftPointer] < pivot do
//do-nothing
end while
while rightPointer > 0 && A[--rightPointer] > pivot do
//do-nothing
end while
if leftPointer >= rightPointer
break
else
swap leftPointer,rightPointer
end if
end while
swap leftPointer,right
return leftPointer
end function
Algoritmo di ordinamento rapido
Usando l'algoritmo pivot in modo ricorsivo, ci ritroviamo con partizioni più piccole possibili. Ogni partizione viene quindi elaborata per l'ordinamento rapido. Definiamo l'algoritmo ricorsivo per quicksort come segue:
Step 1 − Make the right-most index value pivot
Step 2 − partition the array using pivot value
Step 3 − quicksort left partition recursively
Step 4 − quicksort right partition recursively
Pseudocodice di ordinamento rapido
Per approfondire, vediamo lo pseudocodice per l'algoritmo di ordinamento rapido -
procedure quickSort(left, right)
if right-left <= 0
return
else
pivot = A[right]
partition = partitionFunc(left, right, pivot)
quickSort(left,partition-1)
quickSort(partition+1,right)
end if
end procedure
Per conoscere l'implementazione rapida dell'ordinamento nel linguaggio di programmazione C, fare clic qui .