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, digamos pivote, según la partición que se hace y otra matriz contiene valores mayores que el valor de pivote.
Quicksort particiones una array y luego se llama a sí mismo de forma recursiva dos veces para ordenar los dos subarreglos 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 (n2), respectivamente.
Partición en clasificación rápida
La siguiente representación animada explica cómo para encontrar el valor pivote en una matriz.
El valor pivote divide la lista en dos partes. Y de forma recursiva, encontramos el pivote para cada sublista hasta que todas las listas contengan solo un elemento.
Algoritmo de pivote de clasificación rápida
Basándonos en nuestra comprensión del particionamiento en clasificación rápida, ahora intente escribir un algoritmo para él, que es el siguiente.
Step 1 − Choose the highest index value has pivotStep 2 − Take two variables to point left and right of the list excluding pivotStep 3 − left points to the low indexStep 4 − right points to the highStep 5 − while value at left is less than pivot move rightStep 6 − while value at right is greater than pivot move leftStep 7 − if both step 5 and step 6 does not match swap left and rightStep 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 –
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 pivotStep 2 − partition the array using pivot valueStep 3 − quicksort left partition recursivelyStep 4 − quicksort right partition recursively
Pseudocódigo de ordenación rápida
Para obtener más información, veamos el pseudocódigo para una rápida algoritmo de clasificación –
Para conocer la implementación de clasificación rápida en el lenguaje de programación C, haga clic aquí.