In [12]:
using PyCall
@pyimport IPython.display as ipdisplay
In [2]:
# example comparison function
function compare_numbers(a,b)
if a[1] < b[1]
return -1
elseif a[1] > b[1]
return 1
else
return 0
end
end
# example comparison function
function compare_L2(a,b)
if norm(a,2) < norm(b,2)
return -1
elseif norm(a,2) > norm(b,2)
return 1
else
return 0
end
end
# example comparison function
function compare_L1(a,b)
if norm(a,1) < norm(b,1)
return -1
elseif norm(a,1) > norm(b,1)
return 1
else
return 0
end
end
Out[2]:
In [3]:
# insertion sort
# Runtime: O(n^2)
function insertion_sort(A,compare)
n = size(A,1)
for i=2:n
val = A[i,:]
ind = 0
for j=1:i-1 #TODO use binary search instead
if compare(val,A[j,:]) <= 0
ind = j
break
end
end
if ind > 0
A[ind+1:i,:] = A[ind:i-1,:]
A[ind,:] = val
end
end
A
end
Out[3]:
In [25]:
function tostring(a)
s = @sprintf("%d",a[1])
for n in a[2:end]
s = @sprintf("%s, %d",s, n)
end
s
end
Out[25]:
In [24]:
# simple test
n = 10
test1 = int(rand(n) * 100)
println(test1)
test1_sorted = insertion_sort(test1,compare_numbers)
println(test1_sorted)
# duplicates
test2 = [test1; test1]
println(test2)
test2_sorted = insertion_sort(test2,compare_numbers)
println(test2_sorted)
# vector test
println("2d vecs:")
vtest1 = int(rand(n,2)*100)
for i=1:n
println(vtest1[i,:], "(" , norm(vtest1[i,:],2), ")")
end
println("L2:")
vtest1_sorted = insertion_sort(vtest1,compare_L2)
for i=1:n
println(vtest1_sorted[i,:], "(" , norm(vtest1_sorted[i,:],2), ")")
end
println("L1:")
vtest1_sorted_alt = insertion_sort(vtest1,compare_L1)
for i=1:n
println(vtest1_sorted_alt[i,:], "(" , norm(vtest1_sorted_alt[i,:],2), ")")
end
In [26]:
ipdisplay.HTML(@sprintf("<h2>%s</h2>",tostring(test2_sorted)))
Out[26]:
invariant: some claim that should be true at the before the first iteration, at beginning of each iteration, and at the end of the algorithm
initialization: is the invariant true prior to the first iteration?
maintenance: if it is true before an iteration fo the loop, it remains true before the next iteration
termination: when the loop terminates, the invariant gives us a useful property that helps show the algorithm is correct
invariant:_ At the start of each iteration the subarray $A[1 \ldots j-1]$ consists of the elements originally in $A[1 \ldots j-1]$ but in sorted order
initialization: $A[1 \ldots j-1] = A[1]$ which consists of the original $A[1]$ and is in sorted order.
maintenance: informally, during an iteration the elements $A[1 \ldots j]$ are put in order by inserting the original element $A[j]$ into the appropiate locatoin within the sorted elements $A[1 \ldots j-1]$, so that at the beginning of the next iteration ($j = j+1$), the invariant holds.
termination: the loop terminates when $j = n+1$, so that $A[1 \ldots j-1] = A[1 \ldots n]$, which is the entire array sorted. Hence the entire array is sorted and the algorithm is correct.