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 .