Sin embargo, es posible hacer la partición de otra forma, operando sobre la misma lista recibida, reubicando los elementos en su interior, de modo que no se consuma el doble de memoria.
En este caso, tendremos una función _quick_sort, que será muy
similar al de la vista anteriormente, con la particularidad de que en
lugar de recibir listas cada vez más pequeñas, recibirá los índices de
inicio y fin que indican la porción de la lista sobre la que debe
operar.
Habrá, además una función quick_sort, que recibirá la lista más
parámetros, y se encargará de llamar _quick_sort con los índices
correspondientes.
Por otro lado, la función _partition recibirá también los índices de
inicio y fin. En este caso, la función se encargará de cambiar de
lugar los elementos de la lista, de modo que todos los menores al
pivote se encuentren antes de él y todos los mayores se encuentren
después.
Existen varias formas de llevar esto a cabo. Este es un posible diseño
para la función _partition:
- Elegir el pivote como el primero de los elementos a procesar.
- Inicializar un índice menores con el valor del primer elemento de la porción a procesar.
- Recorrer los elementos desde el segundo hasta el último a procesar:
- Si el elemento es menor al pivote, incrementar el índice menores y de ser necesario, intercambiar el elemento para que pase a ser el último de los menores.
- Intercambiar el pivote con el último de los menores
- Devolver la posición del pivote.
El código resultante de este nuevo diseño se reproduce en el código 20.3.
Este código, si bien más complejo, cumple con el objetivo de proveer
un algoritmo de ordenamiento que en el caso promedio tarda T(N) = N x log2 N.