Sí. Puede usar una cola para implementar quicksort. De hecho, no importa qué estructura de datos use. Siempre me ha molestado por qué los libros de texto formales siempre usan un enfoque de pila / recursivo para la clasificación rápida, aunque no es necesario ordenar.
Aquí se explica cómo implementar QuickSort sin usar una pila:
desde cola Cola de importación
- ¿Cuál es una manera simple de implementar la paginación en una matriz en Javascript?
- ¿Cómo visualizo el laberinto que estoy creando?
- Si arr es una matriz de enteros, ¿por qué la expresión ar ++ no es legal?
- ¿Puedo comenzar a aprender visión por computadora sin pasar por algoritmos de aprendizaje automático?
- Cómo habilitar la compresión gzip
partición def (v, comienzo, fin):
pivote = v [final]
nxt = comenzar
para i en rango (comienzo, fin):
si v [i] <= pivote:
v [nxt], v [i] = v [i], v [nxt]
nxt + = 1
v [nxt], v [fin] = v [fin], v [nxt]
return nxt
def quicksort (v):
q = Cola ()
q.put ((0, len (v) -1))
aunque no q.empty ():
(comienzo, fin) = q.get ()
si comenzar> = fin:
continuar
p = partición (v, comienzo, fin)
q.put ((comienzo, p-1))
q.put ((p + 1, final))
v = [4,3,5,1,2]
clasificación rápida (v)
imprimir v
He usado una cola en la implementación anterior, pero podría haber usado cualquier estructura de datos que admita una operación de inserción y recuperación. El orden en que se recuperan los elementos no importa. A Quicksort no le importa en qué rango lo aplicamos primero, esa es su belleza.
Prueba de corrección:
Después de cada iteración del ciclo while, se mantienen los siguientes invariantes:
- La estructura de datos del contenedor (Cola q en la implementación anterior) siempre contiene rangos disjuntos.
- Para cada rango R en q, existe una permutación P tal que después de aplicar P en R para cada rango, obtenemos la matriz ordenada. Intuitivamente, los elementos en cada rango intercambiarán lugares solo con otros elementos del mismo rango.
Puede revisar el código y verificar que las invariantes anteriores se mantienen mediante el bucle while. También tenga en cuenta que la estructura de datos que utilizamos no afecta al bucle invariante.
Lo que estudiamos en nuestros libros de texto es una implementación muy específica de quicksort. El algoritmo en sí es muy liberal sobre cómo lo implementamos.
