Question

b) Prove, using induction, that the following SomeSort function sorts the part of an array from index first to index last in ascending order. You only need to apply induction to the outer for loop. The swap function used in the code below is the same one from part a. (20 marks) 1 void Some Sort (int arr [], int first, int last) { for (int i = first; i < last; i++) { int minpos = i; for (int j = i+1; j <= last; j++) { if (arr[j] = arr[minpos]) { minpos = j; CON O O O swap (arr, i, minpos);

Answer 1

b)
Proof using induction:
   let number of elements SomeSort sorts is n=last-first
now
base case :let n=1
since number of elements 1, the list will be aready sorted
hence true for base case
Induction step:
Assume for n=k it is true,that is outer loop runs k times, at each iteration(from i=first to last) a min value is placed at index i by swap method, which gives sorted list of k values<-(1)
now show that for n=k+1
since, upto n=k, the list will be sorted correctly from (1)
so, the last element (k+1 th element)remaining will be the largest
means the list will be in sorted upto k+1 elements
hence, the method sorts correctly by induction