Consider sorting numbers stored in array by first finding the smallest element of and exchanging it with the element in . Then find the second smallest element of , and exchange it with . Continue in this manner for the first elements of . Write pseudocode for this algorithm, which is known as

. What loop invariant does this algorithm maintain? Why does it need to run for only the first elements, rather than for all elements? Give the best-case and worst-case running times of selection sort in -notation.selection sort

Pseudocode for `SELECTION-SORT(A)`

1
2
3
4
5
6
7
8

for i = 1 to A.length - 1
min = i
for j = i + 1 to A.length
if A[j] < A[min]
min = j
tmp = A[min]
A[min] = A[i]
A[i] = tmp

Loop invariant for the pseudocode will be:

**At the start of the each iteration of the outer for loop of lines 1-8, the subarray consists of smallest elements of , sorted in increasing order.**

The algorithm needs to run for only the first elements, rather than for all elements because the last iteration will compare with and store the largest element among them (consequently largest element of the array) in the last index. So, there is no need to continue the algorithm for all the way to the last element.

For both the best-case (sorted array) and worst-case (reverse sorted array), the algorithm will anyway take one element at a time and compare it with all the other elements. So, the running times for both scenario will be .

**Mathematical Proof:**
We can calculate the cost and times for individual lines of the pseudocode as follows…

Line | Cost | Times |
---|---|---|

1 | ||

2 | ||

3 | ||

4 | ||

5 | ||

6 | ||

7 | ||

8 |

Now, for any arbitrary value of , the inner for loop (line 3-5) compare the previously computed minimum value with all elements in the subarray . So the inner for loop executes times, i.e. for . So, , , … . So,

Therefore, we can calculate the running time as follows..

For best-case scenario, as the array is already sorted, line #5 will not be executed ever. So, . Even with that (and without that for worst-case) the expression of will be reduced to the form , i.e. the algorithm will run at time.