Question

Consider sorting n numbers stored in array A by first finding the smallest element of A and exchanging it with the element in A[1]. Then find the second smallest element of A and exchange it with A[2]. Continue in this manner for the first n-1 elements of A.

a) (10 points) This algorithm is known as the selection sort. Write the pseudo code for this algorithm.
b) (10 points) What loop invariant does this algorithm maintain? Note: You do not have to discuss the three individual properties. You need to only provide the loop invariant.
c) (5 points) Why does it need to run for only the first n-1 elements, rather than for
all n elements?
d) (5 points) Give the best-case and worst-case running times of selection sort
in O-notation. Explain your answers. (You will receive no credit for this question without the explanations for your answers.)

Answer 1

a) Pseudocode of Selection Sort

SELECTION-SORT(A):
  for i = 1 to A.length - 1
      min = i
      for j = i + 1 to A.length
          if A[j] < A[min]
              min = j
      temp = A[i]
      A[i] = A[min]
      A[min] = temp

b) LOOP INVARIANTS :

1.At the start of each iteration of the outer for loop, the subarray A[1..i−1] contains the smallest i−1 elements of the array, sorted in nondecreasing order.

2.At the start of each iteration of the inner for loop, A[min] is the smallest number in the subarray A[i..j−1].

c) Why does it need to run for only the first n-1 elements, rather than for
all n elements?

In the final step, the algorithm will be left with two elements to compare. It will store the smaller one in A[n−1] and leave the larger in A[n]. The final one will be the largest element of the array, since all the previous iteration would have sorted all but the last two elements (the outer loop invariant). If we do it n times, we will end up with a redundant step that sorts a single-element subarray.

d) Best and Worst Case Running Times :

• In the best-case time (the array is sorted), the body of the if is never invoked. The number of operations (counting the comparison as one operation) is:(n-1)(((n+2)/2)+4)
• In the worst-case time (the array is reversed), the body of the if is invoked on every occasion, which doubles the number of steps in the inner loop, that is:(n−1)(n+6)

So Clearly both take Θ(n²) running times.