En este tutorial, compartiremos implementación de clasificación rápida en Python. Quicksort es un algoritmo de clasificación que divide y conquista una lista de entrada.
Funciona seleccionando un elemento pivote de la lista y dividiendo los otros elementos en dos sublistas en función de si son menores o mayores que el pivote.
Luego, el elemento pivote se coloca en su posición final en la lista ordenada y las sublistas se ordenan recursivamente utilizando el mismo proceso.
¿Cómo funciona el algoritmo Quicksort?
Aquí hay un ejemplo más detallado de cómo funciona el algoritmo de clasificación rápida:
- Seleccione un elemento pivote de la lista. Este elemento se utilizará para dividir la lista en dos sublistas.
- Divida la lista en dos sublistas: una sublista izquierda que contiene elementos menores que el pivote y una sublista derecha que contiene elementos mayores que el pivote.
- Ordene las sublistas izquierda y derecha recursivamente usando el mismo proceso.
- Concatene la sublista izquierda ordenada, el elemento pivote y la sublista derecha ordenada para obtener la lista ordenada final.
Quicksort es un algoritmo de clasificación rápido e in situ con una complejidad de tiempo de O(n*log(n)), lo que lo hace ideal para clasificar listas grandes.
Sin embargo, tiene una complejidad de tiempo en el peor de los casos de O(n^2), que puede ocurrir si el elemento pivote no se elige sabiamente o si la lista de entrada ya está parcialmente ordenada.
Pseudocódigo de clasificación rápida
Quicksort es un algoritmo de clasificación popular y efectivo que se usa ampliamente en la práctica debido a su simplicidad y eficiencia.
procedure quicksort(A, lo, hi) is
if lo < hi then
p := partition(A, lo, hi)
quicksort(A, lo, p - 1)
quicksort(A, p + 1, hi)
procedure partition(A, lo, hi) is
pivot := A[hi]
i := lo
for j := lo to hi - 1 do
if A[j] < pivot then
swap A[i] with A[j]
i := i + 1
swap A[i] with A[hi]
return i
Esta implementación de pseudocódigo de ordenación rápida funciona definiendo primero una función de ordenación rápida que toma una matriz A y dos índices, lo y hi, que representan los límites inferior y superior de la subarreferencia que se ordenará.
La función de clasificación rápida primero verifica si es menor que hi y, de ser así, llama a la función de partición para dividir la matriz alrededor de un elemento pivote. Luego llama recursivamente a las sublistas izquierda y derecha obtenidas de la partición.
La función de partición selecciona el último elemento de la matriz como elemento pivote. Use un bucle para dividir la matriz en dos sublistas: una sublista izquierda que contiene elementos menores que el pivote y una sublista derecha que contiene elementos mayores o iguales que el pivote.
Luego, el elemento pivote se coloca en su posición final en la matriz ordenada y la función de partición devuelve el índice del elemento pivote.
Esta implementación de pseudocódigo de ordenación rápida se puede utilizar como punto de partida para implementar el algoritmo en un lenguaje de programación particular.
Implementación de clasificación rápida en Python
Quicksort es un algoritmo de ordenación rápido e in situ que funciona dividiendo la lista de entrada en torno a un elemento pivote y luego ordenando recursivamente las sublistas resultantes. Aquí hay un ejemplo de implementación de clasificación rápida en Python:
def quicksort(arr):
if len(arr) <= 1:
return arr
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)
Esta implementación funciona seleccionando el elemento de la lista de entrada central como pivote y luego creando tres sublistas: una para elementos menores que el pivote, otra para elementos iguales al pivote y otra para elementos mayores que el pivote.
A continuación, ordena recursivamente las sublistas izquierda y derecha y devuelve la concatenación de la lista ordenada de la izquierda, la lista del medio y la lista ordenada de la derecha.
Aquí hay un ejemplo de cómo usar esta función:
arr = [5, 3, 8, 6, 1, 9, 2, 7] sorted_arr = quicksort(arr) print(sorted_arr) # [1, 2, 3, 5, 6, 7, 8, 9]
Esto imprimirá la versión ordenada de la lista de entrada [5, 3, 8, 6, 1, 9, 2, 7]cual es [1, 2, 3, 5, 6, 7, 8, 9].
Complejidad de tiempo Quicksort
En el caso promedio, quicksort es un algoritmo de clasificación rápido e in situ con una complejidad de tiempo de O(nlog(n)). Esto significa que el tiempo que se tarda en ordenar una lista de n elementos mediante ordenación rápida es proporcional a nlog(n).
Esto hace que la ordenación rápida sea adecuada para ordenar listas grandes, ya que la complejidad del tiempo crece lentamente con el tamaño de la entrada.
Sin embargo, la ordenación rápida también tiene una complejidad de tiempo en el peor de los casos de O(n^2), que puede ocurrir si el elemento pivote no se elige sabiamente o si la lista de entrada ya está parcialmente ordenada.
En el peor de los casos, la ordenación rápida puede requerir una complejidad de tiempo O(n^2) para ordenar la lista, lo que puede ser lento para entradas significativas.
Quicksort es un algoritmo de clasificación rápido y eficiente en el caso promedio. Sin embargo, es esencial considerar la complejidad del tiempo en el peor de los casos al elegir un algoritmo de clasificación para una aplicación en particular.
Aplicaciones de clasificación rápida
Quicksort es un algoritmo de clasificación popular y efectivo con varias aplicaciones en varios campos. Algunos ejemplos de aplicaciones donde Quicksort se usa comúnmente incluyen:
- Procesamiento de datos: Quicksort se usa a menudo para clasificar grandes conjuntos de datos en varios campos, como finanzas, atención médica y marketing. Es un algoritmo rápido y eficiente que puede manejar grandes cantidades de datos y es adecuado para la clasificación de datos en el lugar.
- Tecnologia computacional: Quicksort es un algoritmo fundamental en informática y, a menudo, se enseña como un algoritmo de clasificación básico en los cursos de introducción a la informática. También se utiliza en diversas aplicaciones, como la investigación y la implementación de estructuras de datos.
- Desarrollo de software: Quicksort se usa a menudo para ordenar datos en varias aplicaciones, como bases de datos, motores de búsqueda y herramientas de análisis de datos. Es un algoritmo rápido y eficiente, adecuado para clasificar grandes cantidades de datos.
Quicksort es un algoritmo de clasificación eficaz y ampliamente utilizado con muchas aplicaciones en varios campos.
Más tutoriales:
- Comprender cómo funcionan las declaraciones de impresión en Python
- Cómo crear una red neuronal en Python
- Operador O en Python
- Envío de correos electrónicos a través de Python con archivos adjuntos de imagen y PDF
- Lista de palabras reservadas de Python con definiciones y ejemplos
- Cómo crear una matriz vacía en Python