# -*- 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"