DAA - Clasificación rápida

Se utiliza según el principio de divide y vencerás. La clasificación rápida es un algoritmo de elección en muchas situaciones, ya que no es difícil de implementar. Es un buen tipo de propósito general y consume relativamente menos recursos durante la ejecución.

Ventajas

• Está en su lugar ya que usa solo una pequeña pila auxiliar.

• Solo requiere n (log n) hora de ordenar n artículos.

• Tiene un lazo interior extremadamente corto.

• Este algoritmo ha sido sometido a un análisis matemático completo, se puede hacer una declaración muy precisa sobre problemas de rendimiento.

Desventajas

• Es recursivo. Especialmente, si la recursividad no está disponible, la implementación es extremadamente complicada.

• Requiere tiempo cuadrático (es decir, n2) en el peor de los casos.

• Es frágil, es decir, un simple error en la implementación puede pasar desapercibido y hacer que funcione mal.

La clasificación rápida funciona particionando una matriz determinada A[p ... r] en dos submatrices no vacías A[p ... q] y A[q+1 ... r] tal que cada tecla en A[p ... q] es menor o igual que cada clave en A[q+1 ... r].

Luego, las dos submatrices se ordenan mediante llamadas recursivas a Quick sort. La posición exacta de la partición depende de la matriz y el índice dadosq se calcula como parte del procedimiento de partición.

Algorithm: Quick-Sort (A, p, r) 
if p < r then 
   q Partition (A, p, r) 
   Quick-Sort (A, p, q) 
   Quick-Sort (A, q + r, r)

Tenga en cuenta que para ordenar toda la matriz, la llamada inicial debe ser Quick-Sort (A, 1, length[A])

Como primer paso, Quick Sort elige uno de los elementos de la matriz para ordenarlo como pivote. Luego, la matriz se divide a ambos lados del pivote. Los elementos que son menores o iguales que pivotar se moverán hacia la izquierda, mientras que los elementos que son mayores o iguales que pivotar se moverán hacia la derecha.

Particionar la matriz

El procedimiento de particionamiento reorganiza los subarreglos en su lugar.

Function: Partition (A, p, r) 
x ← A[p] 
i ← p-1 
j ← r+1 
while TRUE do 
   Repeat j ← j - 1 
   until A[j] ≤ x  
   Repeat i← i+1 
   until A[i] ≥ x  
   if i < j then  
      exchange A[i] ↔ A[j] 
   else  
      return j

Análisis

La complejidad del peor caso del algoritmo de clasificación rápida es O(n²). Sin embargo, al usar esta técnica, en casos promedio generalmente obtenemos la salida enO(n log n) hora.