Test by Bikram | Data Structures | Test 2 | Question: 30

Question

Meena is working in an IT company as HR manager. She has a large list of potential candidates to be recruited which are all sorted by their names. But she found that due to a bug in software 'O' was treated as '0' by the input reader and hence the sorted list is not correct. What would be the appropriate algorithm to correct the list of candidate profiles?

• A. Quick Sort
• B. Heap Sort
• C. Insertion Sort
• D. Merge Sort

Comments

This is a case of almost sorted array and insertion sort works best in these cases..

https://stackoverflow.com/questions/35884216/why-insertion-sort-is-best-algorithm-for-sorted-or-nearly-sorted-array

Answer 1

Since among the option only Merge sort and Insertion sort are Stable Sort algorithm and it is been said that the list is already sorted by name, so in best case Merge sort takes O(nlogn) time and Insertion sort takes O(n) times.

So that's why it is Insertion Sort.

*NOTE- Stable Sort Algorithm are- Insertion sort, Merge sort, Bubble sort, Selection sort.

Comments

selection sort is not stable

---

Sorry, my mistake, Yes Selection sort is not stable sort algorithm.

Answer 2

in best case merge sort and quick sort are same. but in worst case, merege sort is better. than how insertion sort?

Comments

Time complexity of insertion sort is of same order as the number of inversions in the input. Now, see the maximum possible inversions in this question.

---

when O is treated as 0, all those names will be top in list, but actually it should come after M. so what we have to do is to jump 1-9 and A-M in list and after that we have to put those names with O. This makes number of invertions fixed. Did i think right, sir?

---

Sorted input for quick sort is Worst case input...where as for merge sort it remains O(logn) but for insertion sort it just takes O(n) time i.e one pass...