20.6. Resumen (Algoritmos de Programación con Python)

Los ordenamientos de selección e inserción, presentados en la unidad anterior son ordenamientos sencillos pero que costosos en cantidad de intercambios o de comparaciones. Sin embargo, es posible conseguir ordenamientos con mejor orden utilizando algoritmos recursivos.
El algoritmo Merge Sort consiste en dividir la lista a ordenar hasta que tenga 1 o 0 elementos y luego combinar la lista de forma ordenada. De esta manera se logra un tiempo proporcional a N x logN. Tiene como desventaja que siempre utiliza el doble de la memoria requerida por la lista a ordenar.
El algoritmo Quick Sort consiste en elegir un elemento, llamado pivote y ordenar los elementos de tal forma que todos los menores queden a la izquierda y todos los mayores a la derecha, y a continuación ordenar de la misma forma cada una de las dos sublistas formadas. Puede implementarse de tal forma que opere sobre la misma lista, sin necesidad de utilizar más memoria. Tiene como desventaja que si bien en el caso promedio tarda N x log N, en el peor caso (según cuál sea el pivote elegido) puede llegar a tardar N^2.

# Código 20.3: quicksort.py: Una versión más eficiente de *Quicksort*

#/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.
       Post: la lista está ordenada. """

   quick_sort(lista, 0, len(lista) - 1)

def _quick_sort(lista, inicio, fin):
   """ Función quick_sort recursiva.
       Pre: los índices inicio y fin indican sobre qué porción operar.
       Post: la lista está ordenada.
   """

   # Caso base
   if inicio >= fin:
      return

   # Caso recursivo
   menores = _partition(lista, inicio, fin)
   _quick_sort(lista, inicio, menores - 1)
   _quick_sort(lista, menores + 1, fin)

def _partition(lista, inicio, fin):
   """ Función partición que trabaja sobre la misma lista.
       Pre: los índices inicio y fin indican sobre qué porción operar.
       Post: los menores están antes que el pivote, los mayores después.
       Devuelve: la posición en la que quedó ubicado el pivote. """

   pivote = lista[inicio]
   menores = inicio

   # Cambia de lugar los elementos
   for i in xrange(inicio+1, fin + 1):
      if lista[i] < pivote:
         menores += 1
         if i != menores:
            _swap(lista, i, menores)

   # Pone el pivote al final de los menores
   if inicio != menores:
      _swap(lista, inicio, menores)

   # Devuelve la posición del pivote
   return menores

def _swap(lista, i, j):
   """ Intercambia los elementos i y j de lista. """
   lista[j], lista[i] = lista[i], lista[j]

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.