1. Analyzing Selection Sort. Below is the pseudocode for a sorting algorithm that sorts n elements...

 

Transcribed Image Text:

1. Analyzing Selection Sort. Below is the pseudocode for a sorting algorithm that sorts n elements in a given array A: 1: procedure SELECTIONSORT(A) for i = 1 to n 1 do minIndex = i for j=i+1 ton do if A[j] AlminIndex] then minIndex = j 2: n = length(A) 3: 4: 5: 6: 7: 8: 9: 10: 11: end if Swap A[i] with A[minIndex] end for end for 12: end procedure (a) (3 points) Determine the worst-case running time of SelectionSort and write your answer in e-notation. Justify your answer by showing the number of times the primitive operations are executed in the code above. (b) (3 points) Determine the best-case running time SelectionSort and write your answer in e-notation. (c) (10 points) Prove that the SelectionSort algorithm is correct (i.e. it will output the array in sorted form). That is, for both the inner and outer loops, define a loop invari- ant and show that it meets the required initialization, maintenance, and termination properties. 1. Analyzing Selection Sort. Below is the pseudocode for a sorting algorithm that sorts n elements in a given array A: 1: procedure SELECTIONSORT(A) for i = 1 to n 1 do minIndex = i for j=i+1 ton do if A[j] AlminIndex] then minIndex = j 2: n = length(A) 3: 4: 5: 6: 7: 8: 9: 10: 11: end if Swap A[i] with A[minIndex] end for end for 12: end procedure (a) (3 points) Determine the worst-case running time of SelectionSort and write your answer in e-notation. Justify your answer by showing the number of times the primitive operations are executed in the code above. (b) (3 points) Determine the best-case running time SelectionSort and write your answer in e-notation. (c) (10 points) Prove that the SelectionSort algorithm is correct (i.e. it will output the array in sorted form). That is, for both the inner and outer loops, define a loop invari- ant and show that it meets the required initialization, maintenance, and termination properties.