# -*- coding: cp1252 -*-
import random
import copy
import math
##################################################################
# ALGORITMOS DE ORDENACIÓN
##################################################################
def burbuja(datos):
"""Algoritmo de ordenacion de datos Burbuja doble"""
global n_comps, n_moves
n_comps = n_moves = 0
tam = len(datos)
for i in range(tam, 1, -1):
fin = 1
for j in range(1, i):
n_comps += 1
if datos[j-1] > datos[j]:
n_moves += 3
temp = datos[j]
datos[j] = datos[j-1]
datos[j-1] = temp
fin = 0
if fin:
break
return n_comps, n_moves
def burbuja_doble(datos):
"""Algoritmo de ordenacion de datos Burbuja doble"""
global n_comps, n_moves
n_comps = n_moves = 0
tam = len(datos)
min_i = 1
max_i = tam
fin = 0
while(fin == 0 and min_i < max_i):
fin = 1
j = min_i
while(j < max_i):
n_comps += 1
if datos[j-1] > datos[j]:
n_moves += 3
temp = datos[j]
datos[j] = datos[j-1]
datos[j-1] = temp
fin = 0
j += 1
max_i -= 1
j = max_i
while(j >= min_i):
n_comps += 1
if datos[j-1] > datos[j]:
n_moves += 3
temp = datos[j]
datos[j] = datos[j-1]
datos[j-1] = temp
fin = 0
j -= 1
min_i += 1
return n_comps, n_moves
def seleccion_directa(datos):
"""Algoritmo de ordenacion de datos por Seleccion Directa"""
global n_comps, n_moves
n_comps = n_moves = 0
for i in range(0, len(datos)-1):
min_data = i
for j in range(i+1, len(datos)):
n_comps += 1
if datos[j] < datos[min_data]:
min_data = j
n_moves += 3
temp = datos[i]
datos[i] = datos[min_data]
datos[min_data] = temp
return n_comps, n_moves
def insercion_binaria(data):
"""Algoritmo de ordenacion de datos por insercion binaria"""
global n_comps, n_moves
n_comps = n_moves = 0
for i in range(1, len(data)):
n_moves += 1
temp = data[i]
pos1 = 0
pos2 = i-1
while(pos1 <= pos2):
medio = (pos1 + pos2) // 2
n_comps += 1
if temp < data[medio]:
pos2 = medio - 1
else:
pos1 = medio + 1
j = i - 1
while (j >= pos1):
n_moves += 1
data[j+1] = data[j]
j -= 1
n_moves += 1
data[pos1] = temp
return n_comps, n_moves
def shellsort(datos):
"""Algoritmo de ordenacion de datos Shellsort"""
global n_comps, n_moves
n_comps = n_moves = 0
p = len(datos) // 2
while(p>0):
for i in range(p, len(datos)):
n_moves += 1
temp = datos[i]
j = i
while (j >= p and temp < datos[j-p]):
n_comps += 1
n_moves += 1
datos[j] = datos[j - p]
j -= p
n_comps += 1
n_moves += 1
datos[j] = temp
if (p == 2):
p = 1
else:
p = int(p / 2.2)
return n_comps, n_moves
def heapsort(datos):
"""Algoritmo de ordenacion de datos Heapsort"""
global n_comps, n_moves
n_comps = n_moves = 0
# Crea la estructura de monticulo
tam = len(datos)
puntero = int((len(datos)-1)/2)
while puntero>=0:
cribar(datos, puntero, tam-1)
puntero -= 1
# Ordena monticulo
puntero = len(datos)-1
while puntero>0:
n_moves += 3
temp = datos[puntero]
datos[puntero] = datos[0]
datos[0] = temp
puntero -= 1
cribar(datos, 0, puntero)
return n_comps, n_moves
def cribar(datos, datos_min, datos_max):
global n_comps, n_moves
down = datos_min * 2 + 1
if (down > datos_max):
return
n_moves += 1
temp = datos[datos_min]
while down <= datos_max:
if down < datos_max:
n_comps += 1
if datos[down+1] > datos[down]:
down += 1
n_comps += 1
if temp > datos[down]:
break
n_moves += 1
datos[datos_min] = datos[down]
datos_min = down
down = down * 2 + 1
n_moves += 1
datos[datos_min] = temp
def quicksort(datos):
"""Algoritmo de ordenacion de datos Quicksort"""
global n_comps, n_moves
n_comps = n_moves = 0
quicksort_2(datos, 0, len(datos)-1)
return n_comps, n_moves
def quicksort_2(datos, min_pos, max_pos):
"""Funcion auxiliar del algoritmo de ordenacion Quicksort"""
global n_comps, n_moves
# Condicion de salida recusiva
if min_pos >= max_pos:
return
imin_pos = min_pos
imax_pos = max_pos
mid = datos[int((min_pos+max_pos)/2)]
while imin_pos <= imax_pos:
while datos[imin_pos] < mid:
n_comps += 1
imin_pos += 1
n_comps += 1
while datos[imax_pos] > mid:
n_comps += 1
imax_pos -=1
n_comps += 1
if imin_pos == imax_pos:
imin_pos += 1
imax_pos -= 1
break
if imin_pos < imax_pos:
n_moves +=3
temp = datos[imin_pos]
datos[imin_pos] = datos[imax_pos]
datos[imax_pos] = temp
imin_pos += 1
imax_pos -=1
# Ordena primero el subconjunto mas pequenio para ahorrar saltos recursivos
if imax_pos-min_pos < max_pos-imin_pos:
quicksort_2(datos, min_pos, imax_pos)
quicksort_2(datos, imin_pos, max_pos)
else:
quicksort_2(datos, imin_pos, max_pos)
quicksort_2(datos, min_pos, imax_pos)
def mergesort(datos, cache):
"Algoritmo de ordenacion Mergesort"
global n_comps, n_moves, cache_tam
n_comps = n_moves = 0
cache_tam = cache
m_sort(datos, 0, len(datos)-1)
return n_comps, n_moves
# Algoritmo de ordenacion Mergesort
def m_sort(datos, inicio, fin):
global n_comps, n_moves
# Condición de salida recursiva
if fin <= inicio + 1:
n_comps += 1
if datos[fin] < datos[inicio]:
n_moves += 3
temp = datos[fin]
datos[fin] = datos[inicio]
datos[inicio] = temp
return
mid = int((inicio+fin)/2)
m_sort(datos, inicio, mid)
m_sort(datos, mid+1, fin)
merge_temp(datos, inicio, mid+1, fin)
# Funcion auxiliar merge con pequeña memoria extra
def merge_temp(datos, init1, init2, fin2):
global n_comps, n_moves
memo_temp = cache_tam # Memoria extra para realizar mezcla
temp = range(memo_temp)
fin1 = init2 - 1
i = 0
while init1 <= fin1 and init2 <= fin2:
n_comps += 1
n_moves += 1
if datos[init2] < datos[init1]:
temp[i] = datos[init2]
init2 += 1
else:
temp[i] = datos[init1]
init1 += 1
i += 1
if i >= memo_temp:
inserta(datos, temp, i, init1, fin1, init2, fin2)
init1 = init1 + (init2 - 1 - fin1)
fin1 = init2 - 1
i = 0
inserta(datos, temp, i, init1, fin1, init2, fin2)
# Funcion que inserta la datos temp de longitud len
# al comienzo de dos listas semiordenadas
def inserta(datos, temp, leng, init1, fin1, init2, fin2):
global n_comp, n_moves
init_copy = init1 + (init2 - fin1 - 1) - leng
j = init2 - 1
while fin1 >= init1:
n_moves += 1
datos[j] = datos[fin1]
j -= 1
fin1 -= 1
init1 = init_copy + leng
j = 0
while init_copy < init1:
n_moves += 1
datos[init_copy] = temp[j]
init_copy += 1
j += 1
##################################################################
# FUNCIONES AUXILIARES
##################################################################
def desordena(datos, pares, seed=None):
"""Intercambia entre si las posiciones de num parejas de
elementos de forma aleatoria dentro de la lista de datos"""
tam = len(datos)-1
if seed:
random.seed(seed)
for i in range(pares):
n1 = n2 = 0
while(n1 == n2):
n1 = int(random.uniform(0, tam) + 0.5)
n2 = int(random.uniform(0, tam) + 0.5)
temp = datos[n1]
datos[n1] = datos[n2]
datos[n2] = temp
def datos_aleatorios(tam, rango=9999):
"""Genera una lista de numeros enteros aleatorios en el
rango [0, rango]"""
return [int(random.uniform(0, rango) + 0.5) for i in range(tam)]
def is_sorted(datos):
"""Comprueba si la lista de datos se encuentra ordenada
de menor a mayor. Devuelve True en caso afirmativo"""
tam = len(datos)
old = datos[0]
for i in datos:
if i < old:
raise Exception("NOT SORTED")
i = old
return True
def average_stats(sort, tam, sorted_percent, loops):
"""Tiempo medio de ejecución de un algoritmo de ordenación de datos"""
n_comps_avg = n_moves_avg = total_avg = 0
loops = int(loops)
for i in range(loops):
datos = datos_aleatorios(tam)
if sorted_percent < 100:
quicksort(datos)
pares = tam * sorted_percent/200
desordena(datos, pares)
n_comps, n_moves = sort(datos)
if not is_sorted(datos):
print "ERROR DE ORDENACION"
n_comps_avg += n_comps
n_moves_avg += n_moves
total_avg += n_comps + n_moves
return n_comps_avg/loops, n_moves_avg/loops, total_avg/loops,
def report_1():
loops = 100
for tam in [10, 100, 1000]:
for unsorted_percent in [2, 10, 20, 50, 100]:
if tam * unsorted_percent/200 < 1:
continue
print "\n[hr]\n"
print "[b]Número de elementos en la lista =", tam, "[/b]"
print "[b]Porcentaje de datos desordenados = %d%%[/b]" % unsorted_percent
print "\n[table]"
print "[tr][td][b]Método [/b][/td][td][b] Comparaciones [/b][/td][td][b] Movimientos [/b][/td][td][b] Total [/b][/td][td][b] Total/n [/b][/td][/tr]"
for sort, name in sort_types:
n_comps, n_moves, total = average_stats(sort, tam, unsorted_percent, loops=loops)
print "[tr][td]%-20s[/td][td] %8d[/td][td] %8d[/td][td]%8d[/td][td] %4.2f[/td][/tr]" % (name, n_comps, n_moves, total, float(total)/tam)
print "[/table]"
def report_2():
loops = 100
for sort, name in sort_types:
print "\n[hr]\n"
print "[b]Método de ordenación :", name, "[/b]"
print "\n[table]"
print "[tr][td][b]Elementos [/b][/td][td][b]Desorden [/b][/td][td][b] Comparaciones [/b][/td][td][b] Movimientos [/b][/td][td][b] Total [/b][/td][td][b] Total/n [/b][/td][/tr]"
for tam in [10, 100, 1000]:
for unsorted_percent in [2, 10, 20, 50, 100]:
if tam * unsorted_percent/200 < 1:
continue
n_comps, n_moves, total = average_stats(sort, tam, unsorted_percent, loops=loops)
print "[tr][td]%5d[/td][td] %3d%%[/td][td] %8d[/td][td] %8d[/td][td]%8d[/td][td] %4.2f[/td][/tr]" % (tam, unsorted_percent, n_comps, n_moves, total, float(total)/tam)
print "[/table]"
##################################################################
# PROGRAMA PRINCIPAL
##################################################################
sort_types = [
[burbuja, "Burbuja"],
[burbuja_doble, "Burbuja doble"],
[seleccion_directa, "Selección Directa"],
[insercion_binaria, "Inserción Binaria"],
[shellsort, "Shellsort"],
[heapsort, "Heapsort"],
[lambda(d): mergesort(d, cache=10),"MergeSort (cache=10)"],
[lambda(d): mergesort(d, cache=30),"MergeSort (cache=30)"],
[quicksort, "QuickSort"],
]
random.seed(1)
report_1()
report_2()
