Guía del algoritmo de clasificación rápida de Python
Explore el algoritmo de clasificación rápida en Python. Aprenda la selección dinámica, la partición y la recursividad en este ejemplo de codificación interactivo.
Descripción general
Quicksort es un algoritmo de clasificación extremadamente rápido y ampliamente utilizado. Al igual que la ordenación por fusión, emplea un enfoque de divide y vencerás. Sin embargo, Quicksort clasifica los elementos "en el lugar", lo que hace que sea eficiente en cuanto a memoria.
El algoritmo funciona seleccionando un elemento 'pivote' de la lista. Luego divide los otros elementos en dos subconjuntos: los menores que el pivote y los mayores que el pivote. Este proceso se aplica de forma recursiva a las submatrices.
Aunque Quicksort tiene una complejidad de O(n²) en el peor de los casos, su tiempo de ejecución promedio es O(n log n) y, en la práctica, generalmente supera la ordenación por combinación debido a menores errores de caché y cero gastos generales de creación de matrices temporales.
Código y salida de ejecución
Un script de clasificación rápida recursivo y conciso que utiliza listas por comprensión para una alta legibilidad.
def quicksort(arr):
if len(arr) <= 1:
return arr
else:
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quicksort(left) + middle + quicksort(right)
# Test list
data = [12, 4, 5, 6, 7, 3, 1, 15]
print("Original List:", data)
sorted_data = quicksort(data)
print("Sorted List: ", sorted_data)Original List: [12, 4, 5, 6, 7, 3, 1, 15]
Sorted List: [1, 3, 4, 5, 6, 7, 12, 15]Implementación paso a paso
- Rutinas de clasificación del sistema donde la huella de memoria debe mantenerse al mínimo
- Clasificación de propósito general en marcos de bibliotecas de idiomas estándar
- Enseñanza académica de mecánica de particiones y divide y vencerás recursivo.
Preguntas frecuentes
¿Cómo podemos evitar el peor de los casos de complejidad de O (n²) en Quicksort?
El peor de los casos ocurre cuando el pivote seleccionado es repetidamente el elemento más pequeño o más grande. Para mitigar esto, los desarrolladores utilizan estrategias como elegir un pivote aleatorio o los valores de "mediana de tres".
¿Quicksort es estable?
No, Quicksort estándar es inestable. Durante la partición, los elementos se intercambian en rangos largos, lo que puede alterar el orden relativo de los elementos duplicados.
Temas relacionados
Aprenda a implementar Merge Sort en Python. Un ejemplo interactivo paso a paso de la estrategia de clasificación Divide y vencerás.
Algoritmos de clasificación de PythonExplore los algoritmos de clasificación de Python. Visualice la clasificación por burbujas y la clasificación por combinación de forma nativa dentro del contexto IDE de un navegador.
Algoritmo de búsqueda binaria de PythonBusque listas ordenadas en tiempo logarítmico O (log n). Ejecute y comprenda la búsqueda binaria en Python, incluida la lógica paso a paso, los casos extremos y las optimizaciones.