10.14 Sorting

1. Illustrate the operation of INSERTION-SORT on \([31, 41, 59, 26, 41, 58]\).

   i = 2 (key = 41​)
   Compare with 31: 31 ≤ 41​ → no shifts, insert after 31.
   Array: [31, 41, 59, 26, 41, 58]

   i = 3 (key = 59​)
   Compare with 41: 41 ≤ 59​ → no shifts.
   Array: [31, 41, 59, 26, 41, 58]

   i = 4 (key = 26​)
   Compare and shift while element > key:

   • 59 > 26 → shift 59 right → [31, 41, 59, 59, 41, 58]
   • 41 > 26 → shift 41 right → [31, 41, 41, 59, 41, 58]
   • 31 > 26 → shift 31 right → [31, 31, 41, 59, 41, 58]​
     No more left elements → insert 26​ at front.
     Array: [26, 31, 41, 59, 41, 58]

   i = 5 (key = 41)

   • 59 > 41 → shift 59 right → [26, 31, 41, 59, 59, 58]​
     Now next left is 41 and 41 > 41​ is false → stop and insert key​ after that 41.
     Array: [26, 31, 41, 41, 59, 58]

   i = 6 (key = 58)

   • 59 > 58 → shift 59 right → [26, 31, 41, 41, 59, 59]​
     Next left is 41 and 41 > 58​ is false → insert 58​ after that 41.
     Array: [26, 31, 41, 41, 58, 59]

2. Rewrite the INSERTION-SORT procedure to sort into non-increasing instead of non-decreasing order.

   INSERTION-SORT(A,n)
       for i = 2 to n
           key = A[i]
           // Insert A[i] into the sorted subarray A[1: i - 1].
           j = i - 1
           while j > 0 and A[j] < key
               A[j + 1] = A[j]
               j = j - 1
           A[j + 1] = key
   

3. Consider the sum problem of summing a sequence of numbers \(A=[a_1,a_2,...,a_n]\)

   Input: a sequence of n numbers \(A=[a_{1}, a_{2},..., a_{n}]\).

   Output: the sum of all elements in \(A\).

   1. Implement an iterative version and show the program is correct by using the invariant theorem.

      sumArray(A)
      sum = 0
      i = 1

      {PC} sum = 0 && i = 1
      while i <= |A|
      sum = sum + A[i]
      i = i + 1
      {QC} sum = \(\sum_{j=1}^{|A|} A[j]\)
      return sum

      invariant: 1 <= i <= |A| + 1 && sum = \(\sum_{j=1}^{i-1} A[j]\)

      PC = i = 1 && sum = 0

      QC = i = \(|A|\) +1 && sum = \(\sum_{\{j=1\}}^{\{|A|\}} A[j]\)

      ---

      1. PC \(\implies\) I since \(1 \le i \le |A|+1\) && sum = \(\sum_{j=1}^{|A|} A[j]\)

      2. I && not B \(\implies\) QC
         Since not B \(\iff\) i \(> |A|\) and I holds, we know i = \(|A|+1\) && sum = \(\sum_{j=1}^{|A|+1} A[j]\)

      3. { I && B } { sum = sum + A[i], i = i+1 } { I }
         Lets use i0 and sum0 (A is not changed). We know \(i0 < |A|\).
         Then \(1 \le i0 < |A|+1\) && sum0 = \(\sum_{j=1}^{i0-1} A[j]\)

         Now let do sum = sum + A[i]
         ​\(1 <= i0 < |A|+1\) && sum0 = \(\sum_{(j=1)}^{(i0-1)} A[j]\) && sum = sum0 + A[i]
         But we know who is sum0
         ​\(1 <= i0 < |A|+1\) && sum0 = \(\sum_{(j=1)}^{(i0-1)} A[j]\) && sum = \(\sum_{(j=1)}^{(i0-1)} A[j] + A[i]\)

         So we can compress the sum \(1<=i0< |A|+1\,\&\& \text{ sum} = \sum_{(j=1)}^{(i0+1-1)}A[j]\)

         Simplifying \(1<=i0<|A|+1\,\&\&\text{ sum} = \sum_{(j=1)}^{(i0)}A[j]\)

         Know, we do i=i+1, which says i=i0+1 or i0=i-1, replacing

         \(1<=i-1<|A|+1\,\&\&\text{ sum} = \sum_{(j=1)}^{(i-1)}A[j]\)

         Which implies the invariant

         invariant: \(1 <= i <= |A|+1\) && \(sum = \sum_{j=1}^{i-1} A[j]\)

         Note that:

         • \(1 <= i-1\) is \(2 <= i\) which implies \(1 <= i\)
         • \(i-1 < |A|+1\) implies \(i < |A|+2\) which implies \(i <= |A|+1\)
           1. Implement a recursive version and provide a corrected argument base on the induction principle.

      sumArray(A)
        sumFrom(A, |A|)
      
      sumFrom(A, position)
        if position = 0
          return 0
        else A[position] + sumFrom(A, position - 1)
      
      By induction
      

      By induction
      • sumFrom(A, 0) = 0
      • Let assume sumFrom(A, i) = \(\sum_{j=1}^{i} A[j]\) for all i sumFrom(position) = A[position] + \(\sum_{j=1}^{position-1} A[j]\) by HI
        ==> sumFrom(position) = \(\sum_{j=1}^{position-1+1} A[j]\)

4. Consider the searching problem:

   Input: A sequence of \(n\) numbers \(A=[a_1,a_2,...,a_n]\) and a value \(v\).

   Output: An index \(i\) such that \(v = A[i]\) or the special value NIL if \(v\) does not appear in \(A\).

   1. Write pseudocode for linear search, which scans through the sequence, looking for \(v\).
   2. Using a loop invariant, prove that your algorithm is correct. Make sure that your loop invariant fulfills the three necessary properties.