Proving the correctness of the cocktail shaker sorting algorithm: for (int i = 0; i < (n+1)/2; i++){ for (int j = i; j < n-i-1; j++) if (a[j] > a[j+1]) swap(a[j],a[j+1]); for (int j = n-i-2; j > i; if (a[j] < a[j-1]) swap(a[j],a[j-1]); } (a) the input to the algorithm is an array of n integers that are unsorted a and after the algorithm runs the array will be sorted. state the loop invariant of the outer loop of the cocktail shaker algorithm. (it may be to trace the algorithm on small input to see what it does.) (b) prove the loop invariant using induction over the number of iterations, i. e. i may be used. (c) show how the correctness of the loop invariant shows the correctness of the algorithm.