Aquí está el pseudocódigo [1]
Quicksort (A como matriz, bajo como int, alto como int) {
si (bajo <alto) {
pivot_location = Partición (A, baja, alta)
Quicksort (A, low, pivot_location)
Quicksort (A, pivot_location + 1, high)
}
}
Partición (A como matriz, baja como int, alta como int) {
pivote = A [bajo]
izquierda = baja
para i = bajo + 1 a alto {
si (A [i] <pivote) entonces {
swap (A [i], A [pared izquierda])
leftwall = leftwall + 1
}
}
swap (pivote, A [pared izquierda])
- ¿Qué atajos, términos y algoritmos deben saber los programadores junior para progresar?
- ¿Cuál es la aplicación de la vida real de las estructuras de datos de árbol?
- ¿Cuánto conocimiento de implementación de algoritmos usan realmente los programadores experimentados?
- ¿Cuánto cálculo se requiere para comprender algoritmos y redes de computadoras?
- ¿Puedo obtener una breve descripción general del documento 'Generación precisa de hologramas utilizando el método basado en capas y el algoritmo de transformación de Fourier iterativo'?
volver (izquierda)
Si se mira con cuidado, el número de llamadas recursivas depende del pivote alrededor del cual se reorganiza la matriz. Para lograr la mejor complejidad, el pivote debe ser la mediana de la matriz que resulta en [math] O (nlogn) [/ math].
El peor de los casos ocurre cuando el pivote es más pequeño o más grande en la matriz. Esto divide la matriz en tamaño de [math] 1 [/ math] y [math] n-1 [/ math] respectivamente. Cada llamada [math] i ^ {\ text {th}} [/ math] escanea linealmente una matriz de tamaño [math] ni [/ math], terminando así con [math] O (n ^ 2) [/ math] .
Notas al pie
[1] Quicksort – Algoritmo
