Question

Suppose we are sorting a list of 10 numbers using some of the in-place sorting algorithms discussed in the lectures. After 4 iterations of the algorithm's main loop, the list looks like this: 1 2 3 4 5 0 6 7 8 9 Which statement is correct? Assume selection sort picks smallest items first a.The algorithm might be selection sort, but could not be insertion sort b.The algorithm might be insertion sort, but could not be selection sort c.The algorithm might be either selection sort or insertion sort d.The algorithm is neither selection sort nor insertion sort

Answer 1

b.The algorithm might be insertion sort, but could not be selection sort

Step-by-step explanation:

Selection sort involve picking the smallest items during each iteration and place it in the correct position while starting from the next index during the next iteration.

Insertion sort involve comparing pair of items together and move the wrongly placed item to the correct position.

Based on the given list of 10 numbers:

1 2 3 4 5 0 6 7 8 9

Saying Selection sort was use will be wrong because if selection sort was use, during the first iteration, '0' would be placed at the correct position at the correct position which is before '1'

Saying Insertion sort was use might be correct because taking the elements in pairs and reaching 4 iteration will occur and the position of element '0' would not be reached.

For instance, it could be (1, 2) (2, 3) (3, 4) (4, 5) and this are 4 iteration without reaching the position of element '0'.