MiNaRiYao/sorting.py

# -*- coding: utf-8 -*-
"""
Carlos J Corrada Bravo
Este programa calcula el promedio de tiempo de ejecución de cuatro algoritmos de ordenamiento
La variable maxValor define el valor maximo de los elementos de la lista
La variable largoLista define el largo de las listas a ordenar
La variable veces define las veces que se va a hacer el ordenamiento
Al final se imprimen los promedios de cada algortimo
"""
from random import randint
import time

def isSorted(lista):
    return lista == sorted(lista)

def mergeSort(lista):
  if len(lista)>1:
    mitad = len(lista)//2
    izq = lista[:mitad]
    der = lista[mitad:]

    mergeSort(izq)
    mergeSort(der)

    idx_izq = 0
    idx_der = 0

    idx_lista = 0

    while idx_izq < len(izq) and idx_der < len(der):
      if izq[idx_izq] <= der[idx_der]:
        lista[idx_lista] = izq[idx_izq]
        idx_izq += 1

      else:
        lista[idx_lista] = der[idx_der]
        idx_der += 1

      idx_lista += 1

    while idx_izq < len(izq):
      lista[idx_lista] = izq[idx_izq]
      idx_izq +=1
      idx_lista +=1

    while idx_der < len(der):
      lista[idx_lista] = der[idx_der]
      idx_der += 1
      idx_lista += 1
  return lista

"""La siguiente implementación del algoritmo 'Heapsort'
fue implementada por Miguel E. Cruz Molina, siguiendo
el diseño propuesto en el libro 'Introduction to
Algorithms' (2009, 3rd ed.), de Cormen, T. H. et al."""

def heapSort(lista):
  """Esta función toma una lista de números y los ordena
  usando el algoritmo 'heapsort', que repetitivamente
  convierte a los elementos no-ordenados en un montículo
  maximal y sustituye el elemento mayor por el último."""

  # El algoritmo primero genera un montículo maximal
  #   con los elementos en la lista:
  buildHeap(lista, len(lista) - 1)

  # Por cada uno de los elementos en la lista,
  for i in range(len(lista) - 1, 0, -1):

    # Se sustituye el elemento en la raíz del montículo
    #   (el elemento más grande) con el último,

    #print(lista)
    temp = lista[i]
    lista[i] = lista[0]
    lista[0] = temp
    #print(lista)

    # Y se genera un montículo con los elementos
    #   restantes, hasta terminar con la lista ordenada.

    buildHeap(lista, i)

  return lista

def buildHeap(lista, heapsize):
  """Esta función toma a una lista de números y la
  convierte en una representación lineal de un montículo
  maximal, i.e. un árbol binario en el que el contenido
  de todo nodo padre (de índice k) es mayor al de sus
  hijos (de índices 2k + 1 y 2k + 2). Este proceso se
  realiza recursivamente, desde el penúltimo 'nivel'
  del árbol hasta la raíz, usando la función auxiliar
  'maxHeapify()'. """

  for i in range((heapsize-1)//2, -1, -1):
    maxHeapify(lista, i, heapsize)

def maxHeapify(lista, k, heapsize):
  """Esta función tiene como propósito garantizar que
  la propiedad maximal de un montículo se conserve,
  intercambiando el valor de un nodo padre por el mayor
  valor de entre sus nodos hijos de ser necesario, y
  aplicando el mismo algoritmo sobre el subárbol de ese
  hijo de forma recursiva. La función recibe tres
  argumentos: la lista que contiene el montículo,
  el índice de la raíz del montículo a considerarse,
  y el límite del montículo mayor, que no necesariamente
  es equivalente al largo de la lista."""

  # Primero se identifican los índices hipotéticos
  #   de los nodos hijos:
  l = 2 * k + 1; r = 2 * k + 2; max = k

  # Identificar cuál de los tres nodos tiene el mayor
  #   valor.

  if l < heapsize and lista[max] < lista[l]: max = l
  if r < heapsize and lista[max] < lista[r]: max = r

  # Si el nodo padre no es el mayor, intercambiarlo
  #   por el nodo hijo con mayor valor, y llamar la
  #   función de modo recursivo sobre el subárbol de
  #   ese hijo.

  if max != k:
    temp = lista[k]
    lista[k] = lista[max]
    lista[max] = temp
    maxHeapify(lista, max, heapsize)


def partition(lista, low, high):
    pivot = lista[high]

    i = low - 1

    for j in range(low, high):
        if (lista[j] < pivot):
            i += 1
            lista[i], lista[j] = lista[j], lista[i]

    lista[i+1], lista[high] = lista[high], lista[i+1]

    return i + 1

def quickSortRec(lista, low, high):

    if (low < high):
        p = partition(lista, low, high)

        quickSortRec(lista, low, p - 1)
        quickSortRec(lista, p + 1, high)

    return lista

def quickSort(lista):
	#definan el algoritmo de ordenamiento quicksort
	return quickSortRec(lista, 0, len(lista) - 1)

def insertionSort(lista):

    i = 1
    while i < len(lista):
        if lista[i - 1] > lista[i]:
            j = i - 1
            while j >= 0 and lista[j] > lista[j + 1]:
                lista[j], lista[j + 1] = lista[j + 1], lista[j]
                j -= 1
        i += 1

    return lista

def shellSort(lista):

    gap = len(lista) / 2
    while gap >= 1:
        i = gap
        while i < len(lista):
            if lista[i - gap] > lista[i]:
                j = i - gap
                while j >= 0 and lista[j] > lista[j + gap]:
                    lista[j], lista[j + gap] = lista[j + gap], lista[j]
                    j -= gap
            i += gap
        gap /= 2

    #if isSorted(lista):
        #print "Lista is sorted"
    #else:
        #print "Lista is not sorted"

    return lista

maxValor=1000 	#define el valor maximo de los elementos de la lista
largoLista=1000 #define el largo de las listas a ordenar
veces=100 		#define las veces que se va a hacer el ordenamiento

acumulaMerge=0 	#variable para acumular el tiempo de ejecucion del mergesort
acumulaHeap=0 	#variable para acumular el tiempo de ejecucion del heapsort
acumulaQuick=0 	#variable para acumular el tiempo de ejecucion del quicksort
acumulaShell=0 	#variable para acumular el tiempo de ejecucion del shellsort

for i in range(veces):
	lista = [randint(0,maxValor) for r in range(largoLista)] #creamos una lista con valores al azar

        # creamos copias de la lista para cada algoritmo
        listaMerge = lista[:]
        listaHeap = lista[:]
        listaQuick = lista[:]
        listaShell = lista[:]

	t1 = time.clock() 				#seteamos el tiempo al empezar
	mergeSort(listaMerge) 				#ejecutamos el algoritmo mergeSort
	acumulaMerge+=time.clock()-t1 	#acumulamos el tiempo de ejecucion

#        print isSorted(listaMerge)

	t1 = time.clock()				#seteamos el tiempo al empezar
	heapSort(listaHeap)					#ejecutamos el algoritmo heapSort
	acumulaHeap+=time.clock()-t1 	#acumulamos el tiempo de ejecucion

#        print isSorted(listaHeap)

	t1 = time.clock()				#seteamos el tiempo al empezar
	quickSort(listaQuick)				#ejecutamos el algoritmo quickSort
	acumulaQuick+=time.clock()-t1 	#acumulamos el tiempo de ejecucion

#        print isSorted(listaQuick)

	t1 = time.clock()				#seteamos el tiempo al empezar
	shellSort(listaShell)				#ejecutamos el algoritmo shellSort
	acumulaShell+=time.clock()-t1 	#acumulamos el tiempo de ejecucion

#        print isSorted(listaShell)

#imprimos los resultados
print "Promedio de tiempo de ejecucion de "+ str(veces) +" listas de largo " + str(largoLista)
print "MergeSort " + str(acumulaMerge/veces) + " segundos"
print "HeapSort " + str(acumulaHeap/veces) + " segundos"
print "QuickSort " + str(acumulaQuick/veces) + " segundos"
print "ShellSort " + str(acumulaShell/veces) + " segundos"