Estructura de datos y algoritmos: clasificación rápida

La clasificación rápida es un algoritmo de clasificación altamente eficiente y se basa en la partición de una matriz de datos en matrices más pequeñas. Una matriz grande se divide en dos matrices, una de las cuales contiene valores más pequeños que el valor especificado, por ejemplo, pivote, en función de la cual se realiza la partición y otra matriz contiene valores mayores que el valor de pivote.

Quicksort divide una matriz y luego se llama a sí mismo de forma recursiva dos veces para ordenar las dos submatrices resultantes. Este algoritmo es bastante eficiente para conjuntos de datos de gran tamaño ya que su complejidad promedio y en el peor de los casos son O (n ² ), respectivamente.

Partición en clasificación rápida

La siguiente representación animada explica cómo encontrar el valor de pivote en una matriz.

El valor de pivote divide la lista en dos partes. Y de forma recursiva, encontramos el pivote para cada sublista hasta que todas las listas contienen solo un elemento.

Algoritmo de pivote de clasificación rápida

Basándonos en nuestra comprensión del particionamiento en orden rápido, ahora intentaremos escribir un algoritmo para él, que es el siguiente.

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 dinámico de clasificación rápida

El pseudocódigo para el algoritmo anterior se puede derivar 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 clasificación rápida

Usando el algoritmo de pivote de forma recursiva, terminamos con particiones posibles más pequeñas. Luego, cada partición se procesa para una clasificación rápida. Definimos el algoritmo recursivo para la ordenación rápida de la siguiente manera:

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 clasificación rápida

Para profundizar más, veamos el pseudocódigo para el algoritmo de clasificación 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 conocer la implementación de ordenación rápida en el lenguaje de programación C, haga clic aquí .