SI335: Basic iterative sorting: insertionSort & selectionSort [HW]

Name: ____________________________________________________ Alpha: _____________________

Describe help received: _________________________________________________________________
Per-problem assessment: • 5 (Perfect): Correct solution • 4 (Good effort): Good effort, solution may or may not be correct. • 2 (Poor effort): Some basic misunderstandings demonstrated that could have been cleared up by reading the notes or giving a serious try. • 0 (No effort): No progress towards a solution.

Problem 0 (assessment: self_ final_)

Look back at the loop invariants we came up with in class for insertionSort and selectionSort. Both algorithms have the same outer loop:

for i from 0 to n-2 do

Could I run insertionSort for $k$ iterations, and then switch over to selectionSort with $i = k$ and be guaranteed to end up with correctly sorted output? Justify your answer!
Could I run selectionSort for $k$ iterations, and then switch over to insertionSort with $i = k$ and be guaranteed to end up with correctly sorted output? Justify your answer!

Problem 1 (assessment: self_ final_)

Suppose that we want to sort an array $A$ of length $n$, in which each element of $A$ is itself an array of $n$ integers. We will define "<" for these arrays as

Algorithm: lt(a,b)
Inputs: a and b, both n-element arrays of integers
Output: true if a is "less than" b, false otherwise

k = 0;
while k < n and a[k] = b[k] do
  k = k + 1

if k < n and a[k] < b[k]
  return true
else
  return ralse

Analyze the worst-case running time of insertionSort in this case, i.e. with an n-element array $A$, each element of which is array of $n$ integers, using the above algorithm as "<".
Note1: You must justify both your lower bound and upper bound!
Note2: Assume the elements of $A$ are pointers to arrays of ints, so that swapping two elements of $A$ is a constant time operation.

Problem 1 (assessment: self_ final_)

From Wikipedia: Gnome sort (or Stupid sort) is a sorting algorithm originally proposed by an Iranian computer engineer Dr. Hamid Sarbazi-Azad (Professor of Computer Engineering at Sharif University of Technology) in 2000 and called "stupid sort".

The following sorting algorithm is called "Gnomesort":

Algorithm: gnomesort(A,n)
Input: array A of n elements	
Output: side effect - the elements of A are sorted
k = 0
while k < n
  if k > 0 and A[k] < A[k-1]
    swap(A[k],A[k-1])
    k--
  else
    k++

The beautiful thing about Gnomesort is that it's not at all clear that this thing ever halts, much less halts with the array in sorted order. How can we convince ourselves that this algorithm is correct. Consider the following function \[ f(A,n,k) = (n-k) + 2*\# \text{ pairs $i,j$ such that $0 \leq i \lt j \lt n$ and $A[j] \lt A[i]$} \]

So, for example, if $A=$

$, n=4, k = 2$ then

(8,5), (8,6), (8,4), (5,4), (6,4) are out of order, so $f(A,n,k) = (4 - 2) + 2*5 = 12$.

Compute the value of $f$ in the example below:

$A=$ , n = 6, k = __3__ and $f(A,n,k) = $ ___________
After one iteration of gnomesort, we would have:

$A=$ n = 6, k = _____ and $f(A,n,k) = $ ___________
After another iteration of gnomesort, we would have:

$A=$ n = 6, k = _____ and $f(A,n,k) = $ ___________
Prove that $f(A,n,k)$ gets smaller every time the body of the gnomesort loop is executed.
How does this prove that the algorithm halts?

Problem 0 (assessment: self_______ final_______)

Problem 1 (assessment: self_______ final_______)

Problem 1 (assessment: self_______ final_______)

Problem 0 (assessment: self_ final_)

Problem 1 (assessment: self_ final_)

Problem 1 (assessment: self_ final_)