#Sorting

Question

Which of the following is/are the status of the array after some iteration of a sorting algorithm, which sorting algorithm it might be?

14  42  17  72  12  10  5  1

1. Heap sort

2. Merge sort

3. Selection sort

4. Insertion sort

Comments

what is the initial array?

---

The question is only this.

No initial array is given in the question.

---

then close that question.... with out knowing the initial status of array, how can you derive the given status of array

---

There is no problem with the question.

---

I think it can be selection or insertion..

The sorting type(increasing or decreasing order) is not mentioned..it can be anything..so I can assume both possibilities

In selection sorting, we try to find the min element (or max depending on the type of sorting we are doing-ascending or descending) and put in at then end. I assume that the sorting here is descending.

Then we find the 2nd min and put it in the 2nd last pos and so on..

In this array 14  42  17  72  12  10  5  1  ..it seems that upto the 4^th min element iterations have been done i.e. 12 is placed in the correct place.

In insertion sorting, upto 2nd place the sorting is done..

It is like sorting a subarray from pos 1 to k^th place. (14,42) is sorted if we consider sorting as ascending one..)

What is the answer given?

---

why not heap?

14,42,17,72 ---- in Min Heap after taking out 1,5,10,12

---

Shaik Masthan Yes i think heap can be another possibility ..

---

All is the answer.

---

if it is more than one iteration, then Mergesort can't be the answer.

( i am considering single element passes on 1st iteration )

---

May be the array was initially like

42 14 72  17  12  10  5  1 (there might be other possibilites)

If merge sort is also an answer then I guess the Division part of the divide and conquer mechanism has been done and then Merge is called for 2 times i.e. for merging (42),(14) to make it sorted to (14,42) and on (72),(17) to make it (17,72).

---

Yes but only if they are using recursion

Since they said iterations i assumed that iterative merge sort is used in which in first iteration pairs are sorted