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. Write pseudocode for this algorithm, which is known as selection sort. What loop invariant does this algorithm maintain? Why does it need to run for only the first n − 1 elements, rather than for all n elements? Give the best–case and worst–case running times of selection sort in Θ–notation.

Answer 1

1. create the first array A

2. create the second array A1, the same length as array A.

3. create a loop to iterate over both arrays for a number of times specific to the length of the arrays, with a condition to get and pop only the minimum value of which arrays for every loop.

4. save both items to "a" for minimum value A and "b" for minimum value A1.

5. call a function to push the "a" variable value to A1 and "b" variable value to the array A.

Step-by-step explanation:

This code would interchange the values of both arrays, the best-case scenario for the code is O( n ) where n is the number of items in both arrays and worst is the best-case multiplied by the number of time to compare all the items with the minimum value.