Algoritmos de Programación con Python

20.5. Una versión mejorada de Quick sort

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:

  1. Elegir el pivote como el primero de los elementos a procesar.
  2. Inicializar un índice menores con el valor del primer elemento de la porción a procesar.
  3. 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.
  4. Intercambiar el pivote con el último de los menores
  5. 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.


Copyright (c) 2011-2014 Rosita Wachenchauzer, Margarita Manterola, Maximiliano Curia, Marcos Medrano, Nicolás Paez. La copia y redistribución de esta página se permite bajo los términos de la licencia Creative Commons Atribución - Compartir Obras Derivadas Igual 3.0 siempre que se conserve esta nota de copyright.