Quadratic sorts behavior

Question

Is below problem meaningful? I am not able to get any logic behind it. Either am missing something or the problem is real crap.

Suppose one is applying a particular quadratic sorting algorithm to an array of integers. After four iterations the array stand as:
1,2,3,4,5,6,7,8,9

Which of the following may be in use?

1. Selection sort that selects the largest element in each iteration
2. Insertion sort
   • A.  i or ii
   • B. ii only
   • C. ii only
   • D. None of these

Answer 1

Its a perfectly Logical Question. 

To understand this question, you have to understand the logic behind the Selection Sort and Insertion Sort.

Selection Sort: In the first iteration it select the first element of the array (say p), and compare p to the rest of the element in the array. And if there is any element exist which is greater than p then it perform a swap and again start comparing with the new value of p.

The given sequence (1, 2, 3, 4, 5, 6, 7, 8) can not be achieved by using Selection Sort (In the question its given that it select largest element in each iteration). Because  this will put 8 on the first position after the first iteration. But 8 is in the end. Hence it can not possible. 

Insertion Sort : This is based on the partition. Lets take sequence as 4,2,3,1,5,6,7,8 and apply insertion sort. After 4 iteration you will get 1,2,3,4,5,6,7,8. (I am taking this because in the question its not given that insertion is sorting element in increasing order or decreasing order). 

Hence Answer would be (B) ii Only. 

Comments

@Arjun sir, please verify this. 

---

The answer given without explanation is (A). However I believe you are correct.

---

@rude will really position of of Largest element will change logic of Selection sort. I think no. Selection sort and bubble sort will not only differ by putting smallest in first and largest in last respectively.

Core of selection sort is it takes first element as min and check it with others and finally swaps. Will algo change if it do this thing from last element??

Same case with selection sort with largest element.

So i think we can use any algo given.

---

yes @rude I too think both sorting can be applied

---

@sonu dude read this. Do you understand the meaning of that word in question in selection sort part, select the highest number in each iteration, What is means? is that meaningless? thay have put that just like that? 

@srestha Please read the basic strategies about selection and insertion. We can discuss about it.

---

It says to select the largest element in each iteration- but never says that goes to left most position. So, A should be the answer- both sorting works here.

---

Sir Have you ever seen in selection sort, that selected element put in right most position. Here I am not saying it can not be done, But what I am saying that this is not the real/actual strategy of selection sort. See the wikipedia page, it has shown that whatever element you select in the first iteration, put that in first position. I have read Sorting and Searching from Donald Knuth Vol 3. I know what i am talking. Rest is your choice. Thx,. 

---

Yes, in fact I always used that implementation during my bachelors. Regarding actual/real strategy I do not know and 1 question was asked in last GATE also for bubble sort.

---

@Arjun @srestha @sonu Can you give me a single link, where you can show that in selection algorithm they are putting element in last. I mean can you quote any standard book.

What I am saying that Every sorting techniques have, its own strategies, bubble sort and heap sort fix the last data item first. Now the next you say that why can not i apply bubble sort from right to left. I can code that. Its is possible. Is not it?

---

@Arjun Sir Sorting algo like selection and bubble and insertion will be compared and understood by how many swaps and comparision they are doing. Either they do  this thing from any side.. does it really matters?

I think no. becoz core concept is still there..Ryt sir?

---

both points are correct...(1) If maximum element is selected and put on left it will result in descending order (2) If maximum element is selected and put on right, it will result in ascending order. Now I just wish GATE setters do not ask such vague questions, so that even people knowing all this end up loosing marks...