``````

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]:

compare_L1 (generic function with 1 method)

``````
``````

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]:

insertion_sort (generic function with 1 method)

``````
``````

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]:

tostring (generic function with 1 method)

``````
``````

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

``````
``````

[44,32,65,98,6,59,98,8,29,99]
[6,8,29,32,44,59,65,98,98,99]
[6,8,29,32,44,59,65,98,98,99,6,8,29,32,44,59,65,98,98,99]
[6,6,8,8,29,29,32,32,44,44,59,59,65,65,98,98,98,98,99,99]
2d vecs:
[78 72](106.1508360777248)
[20 23](30.479501308256342)
[3 55](55.08175741568164)
[18 90](91.78235124467014)
[39 56](68.24221567329126)
[60 1](60.00833275471)
[14 73](74.33034373659254)
[96 36](102.52804494381036)
[25 68](72.44998274671981)
[40 49](63.25345840347387)
L2:
[20 23](30.479501308256342)
[3 55](55.08175741568164)
[60 1](60.00833275471)
[40 49](63.25345840347387)
[39 56](68.24221567329126)
[25 68](72.44998274671981)
[14 73](74.33034373659254)
[18 90](91.78235124467014)
[96 36](102.52804494381036)
[78 72](106.1508360777248)
L1:
[20 23](30.479501308256342)
[40 49](63.25345840347387)
[3 55](55.08175741568164)
[39 56](68.24221567329126)
[60 1](60.00833275471)
[25 68](72.44998274671981)
[14 73](74.33034373659254)
[78 72](106.1508360777248)
[18 90](91.78235124467014)
[96 36](102.52804494381036)

``````
``````

In [26]:

ipdisplay.HTML(@sprintf("<h2>%s</h2>",tostring(test2_sorted)))

``````
``````

Out[26]:

6, 6, 8, 8, 29, 29, 32, 32, 44, 44, 59, 59, 65, 65, 98, 98, 98, 98, 99, 99

``````

## loop invariants:

• used to show an algorithm is correct, similar to proof by induction, but instead of doing to infinity we only go to the end of the loop

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

## loop invariants for insertion sort:

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.