Ver índice de contenidos del libro

20.4. ¿Cuánto cuesta el Quick sort?

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
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.