A primera vista, la ecuación del tiempo consumido parece ser la misma que en el Mergesort: Una partición que se hace en tiempo líneal más dos llamadas recursivas a mitades de la lista original.
Pero el problema acá es que la partición tomando como pivote lista[0]
no siempre parte la lista en mitades: puede suceder (y ese es el peor
caso) que parta a la lista en ([], [lista[0]], lista[1:]) (esto es lo
que pasa cuando la lista está ordenada de entrada, para el algoritmo
presentado), y en ese caso se comporta como selección.
En cambio, cuando la lista tiene números ubicados de manera arbitraria
dentro de ella, podemos imaginar un comportamiento parecido al del
Mergesort, y por lo tanto ahí sí T(N) = N ∗ log2 N.
Si analizamos el espacio que consume, el código mostrado en código 20.2 crea nuevas listas a cada paso, con lo cual al igual que el Merge sort utiliza el doble de memoria.
# Código 20.2: quicksort_copia.py: Una primera aproximación al *Quick sort*
#!/usr/bin/env python
#encoding: latin1
def quick_sort(lista):
""" Ordena la lista de forma recursiva.
Pre: los elementos de la lista deben ser comparables.
Devuelve: una nueva lista con los elementos ordenados. """
# Caso base
if len(lista) < 2:
return lista
# Caso recursivo
menores, medio, mayores = _partition(lista)
return quick_sort(menores) + medio + quick_sort(mayores)
def _partition(lista):
""" Pre: lista no vacía.
Devuelve: tres listas: menores, medio y mayores. """
pivote = lista[0]
menores = []
mayores = []
for x in xrange(1, len(lista)):
if lista[x] < pivote:
menores.append(lista[x])
else:
mayores.append(lista[x])
return menores, [pivote], mayores