Algorithm SelectionSort(A[0..n-1])

//input:An array A[0..n-1]

//output:Array A[0..n-1] sorted in ascending order

for i <-- 0 to n - 2 do

min <--- i

for j <----- i +1 to n-1 do

if A[j] < A[min] min<--- j

swap A[i] and A[min]

1. Trace this algorithm with the following array. Imagine that you have a print statement after the swap statement in above algorithm. Show the array after each execution of the swap statement. Show your work in detail and neatly.

5 4 7 3 1

1. How many comparisons in total you made i.e. how many times the comparison statement A[i] < A[min] is executed?

2. How many swaps in total you made i.e. how many times the swap statement swap A[i] and A[min] is executed?

3. Is selection sort stable? Apply the algorithm in the array of 2 2 1 3 5 and justify your answer.