Estrutura de dados e algoritmos - classificação rápida

A classificação rápida é um algoritmo de classificação altamente eficiente e é baseado no particionamento de array de dados em arrays menores. Uma grande matriz é particionada em duas matrizes, uma das quais mantém valores menores do que o valor especificado, digamos, pivô, com base na qual a partição é feita e outra matriz mantém valores maiores que o valor pivô.

O Quicksort particiona um array e, em seguida, chama a si mesmo recursivamente duas vezes para classificar os dois subarrays resultantes. Este algoritmo é bastante eficiente para conjuntos de dados de grande porte, pois sua complexidade média e de pior caso são O (n ² ), respectivamente.

Partição em classificação rápida

A representação animada a seguir explica como encontrar o valor pivô em uma matriz.

O valor pivô divide a lista em duas partes. E recursivamente, encontramos o pivô para cada sublista até que todas as listas contenham apenas um elemento.

Algoritmo de Pivô de Classificação Rápida

Com base em nosso entendimento de particionamento em classificação rápida, agora tentaremos escrever um algoritmo para ele, que é o seguinte.

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

Pseudocódigo de Pivô de Classificação Rápida

O pseudocódigo para o algoritmo acima pode ser derivado como -

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 de classificação rápida

Usando o algoritmo de pivô recursivamente, acabamos com partições menores possíveis. Cada partição é então processada para classificação rápida. Definimos algoritmo recursivo para quicksort da seguinte forma -

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

Pseudocódigo de classificação rápida

Para obter mais informações, vamos ver o pseudocódigo para algoritmo de classificação rápida -

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

Para saber sobre a implementação de classificação rápida na linguagem de programação C, clique aqui .