def insertion_sort(A):
j = 1
while j < len(A):
key = A[j]
i = j - 1
while (i >= 0) and (A[i] > key):
A[i + 1] = A[i]
i = i -1
A[i + 1] = key
j = j + 1
B = [5, 4, 6, 3, 7, 2, 8, 1, 9]
print B
insertion_sort(B)
print B
[5, 4, 6, 3, 7, 2, 8, 1, 9] [1, 2, 3, 4, 5, 6, 7, 8, 9]
Invariante de ciclo
Al comienzo de cada iteración del ciclo externo el subarreglo $A[0..j-1]$ consiste de los elementos originalmente en $A[0..j-1]$ pero ordenados.
La siguiente función implementa la comprobación correspondiente al invariante de ciclo.
def invariant(A, original_A):
l1 = list(A)
l2 = list(original_A)
l2.sort()
return l1 == l2
invariant([1, 2, 3, 4], [4, 3, 2, 1])
True
invariant([1, 2, 3, 4, 4], [4, 3, 2, 1, 5])
False
La siguiente función incluye aserciones para verificar que el invariante de ciclo se cumpla. Si la función es correcto, estas aserciones no deberían fallar.
def right_insertion_sort(A):
original_A = list(A)
j = 1
assert invariant(A[0:j], original_A[0:j])
while j < len(A):
assert invariant(A[0:j], original_A[0:j])
key = A[j]
i = j - 1
while (i >= 0) and (A[i] > key):
A[i + 1] = A[i]
i = i -1
A[i + 1] = key
j = j + 1
assert invariant(A[0:j], original_A[0:j])
B = [5, 4, 6, 3, 7, 2, 8, 1, 9]
right_insertion_sort(B)
print B
[1, 2, 3, 4, 5, 6, 7, 8, 9]
La siguiente función incluye un error, por lo tanto la aserción para comprobar el invariante de ciclo falla. Esto genera una excepción que es capturada para imprimir un mensaje y el estado de las variables.
def wrong_insertion_sort(A):
original_A = list(A)
j = 1
try:
assert invariant(A[0:j], original_A[0:j])
while j < len(A):
assert invariant(A[0:j], original_A[0:j])
key = A[j]
i = j - 1
while (i >= 0) and (A[i] < key):
A[i + 1] = A[i]
i = i - 1
A[i + 1] = key
j = j + 1
assert invariant(A[0:j], original_A[0:j])
except AssertionError:
print "Error en el invariante de ciclo!"
print "j=", j
print "i=", i
print "A=", A
print "Original A=", original_A
B = [5, 4, 6, 3, 7, 2, 8, 1, 9]
wrong_insertion_sort(B)
Error en el invariante de ciclo! j= 2 i= 0 A= [5, 4, 6, 3, 7, 2, 8, 1, 9] Original A= [5, 4, 6, 3, 7, 2, 8, 1, 9]
class Counter:
'''
Class Counter
Implements a step counter, which is used to compute the number of basic operations performed in
a particular call to a function.
'''
def __init__(self):
self.steps = 0
def reset(self):
self.steps = 0
def count(self):
self.steps += 1
def print_steps(self):
print "Number of steps =", self.steps
def acct_insertion_sort(A, acct):
j = 1; acct.count()
acct.count()
while j < len(A):
acct.count()
key = A[j]; acct.count()
i = j - 1; acct.count()
acct.count()
while (i >= 0) and (A[i] > key):
acct.count()
A[i + 1] = A[i]; acct.count()
i = i -1; acct.count()
A[i + 1] = key; acct.count()
j = j + 1; acct.count()
B = [5, 4, 6, 3, 7, 2, 8, 1, 9,10]
acct = Counter()
acct_insertion_sort(B, acct)
acct.print_steps()
Number of steps = 104
Ahora vamos a analizar el comportamiento del algoritmo cuando el tamaño de la entrada varía. La siguiente función genera arreglos al azar de tamaño 1 a n, llama la función acct_insertion_sort(l, acct)
y contabiliza el número de pasos.
import random as rnd
def exper_analysis(n):
results = []
acct = Counter()
for i in range(n):
l = range(i)
rnd.shuffle(l)
acct.reset()
acct_insertion_sort(l, acct)
results.append(acct.steps)
return results
print exper_analysis(10)
[2, 2, 11, 20, 23, 41, 59, 80, 80, 116]
import numpy as np
import pylab as pl
pl.clf()
x = np.arange(100)
y = np.array(exper_analysis(100))
pl.plot(x, y, 'k.')
[<matplotlib.lines.Line2D at 0x1089abf90>]