200 views

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?

1. Quick Sort
2. Heap Sort
3. Insertion Sort
4. Merge Sort
| 200 views
+2

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

+1 vote

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.

by (173 points)
selected by
0
selection sort is not stable
0
Sorry, my mistake, Yes Selection sort is not stable sort algorithm.
in best case merge sort and quick sort are same. but in worst case, merege sort is better. than how insertion sort?
by Active (3.6k points)
+3

My intuition about insertion sort is "When people manually sort cards in a bridge hand, most use a method that is similar to insertion sort." and also if your input data is already sorted  the insertion sort will be fast.

+1
sorry sir but actually i applied nothing special logic. just comparision of TC. :-P but my be you are right. as sorting is done manually than we can not appy sort like merge, quick etc. they are used programmatically
0

Yes both merge sort and Quick sort are comparison based sorting Algorithms they are not work manually.

comparison sort meaning that it can sort items of any type for which a "less-than" relation (formally, a total order) is defined. so in this question there is no such case like less than etc that why i choose insertion sort as answer.

https://en.wikipedia.org/wiki/Merge_sort

https://en.wikipedia.org/wiki/Quicksort

0
This question is not about manual sorting. Merge/Heap gives $O(n \log n)$ here. But insertion sort performs better- have to show how.
0
then show some path sir..
+2
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.
0
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?
0
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...