El algoritmo de clasificación rápida es un algoritmo de división y conquista que clasifica la secuencia dada en su lugar, lo que significa que no requiere almacenamiento adicional, ya que necesitamos en el orden de fusión.
La idea básica es dividir la secuencia (por conveniencia, diré matriz) en 2 subarreglos alrededor de un elemento (un elemento particular de la matriz dada) que se llama pivote, de modo que los elementos en un subarreglo inferior sean menores que el pivote. El elemento y los elementos en una sub-matriz superior son más altos que el elemento pivote.
[código]
clasificación rápida (A, p, q)
si (p <q)
entonces r = partición (A, p, q)
clasificación rápida (A, p, r-1)
clasificación rápida (A, r + 1, q)
[/código]
la llamada inicial típica es quicksort (A, 0, n) // n = longitud de la matriz
- ¿Por qué Java utiliza diferentes algoritmos de clasificación para diferentes tipos de datos?
- ¿Cuál es el algoritmo para resolver el buscaminas?
- ¿Qué tan difícil sería para un novato la 'Introducción a los algoritmos' de Thomas H. Cormen?
- Quiero aprender más sobre algoritmos, pero no sé por dónde empezar. ¿Me puede dar algunas instrucciones o consejos? Gracias.
- ¿Cómo podemos decir que la búsqueda binaria es un algoritmo rápido?
[código]
partición (A, p, q)
x = A [p]
i = p
para j = p + 1 a q
si (A [j] <= x)
i = i + 1
intercambio (A [i], A [j])
intercambio (A [p], a [i])
regreso yo
[/código]
Explicación:
supongamos que la matriz es 7 11 14 6 9 4 3 12
La clasificación de burbujas simplemente intercambia los elementos adyacentes si los dos que está mirando están ordenados incorrectamente. Continúa avanzando en la lista y continuará hasta que todo esté ordenado. Ahora, repasemos el código que escribimos.
Esto iniciará un índice ‘a’ que apunta al primer elemento de la lista. El bucle interno crea un segundo índice que va al último elemento (tamaño – 1) y lo disminuirá hasta llegar a ‘a’. El primer paso será comparar el último elemento con el penúltimo elemento e intercambiarlos si es necesario. ‘b’ se disminuye y se comparan el segundo del último y el tercero del último. Esto continúa hasta que se comparan el primer y el segundo elemento de la lista. Una vez que ‘b’ ha alcanzado su condición de terminación, incrementamos ‘a’ y continuamos. Este incremento de ‘a’ es posible ya que sabemos que el elemento más pequeño de la lista se distribuirá correctamente al primer elemento, por lo que no sería necesario que ‘b’ verifique valores menores que ‘a’.
Aquí hay un pequeño ejemplo para ilustrar la idea (el número subrayado es ‘a’ , el número en cursiva es b, los números en negrita son dos comparados )
Lista sin clasificar:
4 6 2 1 3 5
Primer pase:
4 6 2 1 3 5 – inicialmente ‘a’ apunta al primer elemento, ‘b’ al último
4 6 2 1 5 3 – los dos últimos elementos se intercambian
4 6 2 1 5 3 – ‘b’ se reduce y se comparan dos elementos nuevos
4 6 2 1 5 3 – no se realiza ningún intercambio y ‘b’ se reduce nuevamente
4 6 1 2 5 3 – los siguientes dos han sido intercambiados
4 6 1 2 5 3 – ‘b’ se vuelve a disminuir
4 1 6 2 5 3 – se realiza otro intercambio
4 4 1 6 2 5 3 – ‘b’ se reduce
1 4 6 2 5 3 – el intercambio se realiza y ‘b’ ya no se puede disminuir
1 4 6 2 5 3 – ‘a’ se incrementa y ‘b’ se restablece al final
…
1 2 4 6 3 5 – Después del segundo pase
…
1 2 3 4 6 5 – Después del tercer pase
…
1 2 3 4 5 6 – Después del cuarto pase
Puede ver en este breve ejemplo que podemos ver cómo el tipo de burbuja ‘burbujeará’ el elemento más pequeño hacia el frente y asegúrese de que los elementos de menos de ‘a’ estén bien.
En orden, podemos decir que la peor complejidad de tiempo para el orden rápido es O (n ^ 2) y el mejor / promedio es O (nlogn), mientras que Bubble sort tiene O (n ^ 2) en todos los casos.
