GATEBOOK exam

Question

Suppose we are sorting an array of ten integers using a some quadratic sorting algorithm. After four iterations of the algorithm's main loop, the array elements are ordered as shown here: 1 2 3 4 5 0 6 7 8 9 Which statement is correct? (Note: Our selection sort picks largest items first.)

A) The algorithm might be either selection sort or insertionsort.

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

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

D) The algorithm is neither selection sort nor insertion sort.

Answer 1

Well, Algorithm can be both Selection sort and Insertion Sort.  (hence option A)

Insertion Sort : if the original array is $4,3,2,1,5,0,6,7,8,9$, then after 4 iterations of insertion sort, we get $1,2,3,4,5,0,6,7,8,9$.

Selection Sort : We pick the largest element of the array and place it towards the end, and after doing this $n$ times array is sorted. As, last 4 elements hold this property that at the end of each iteration an element should be towards end. Hence, it can be selection sort (modified). Since this selection sort starts with the largest items, the fully-sorted segment would actually grow from the back of the list.