The Gateway to Computer Science Excellence
+2 votes

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
in Programming by Veteran (74.8k points) | 200 views

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

2 Answers

+1 vote
Best answer

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
selection sort is not stable
Sorry, my mistake, Yes Selection sort is not stable sort algorithm.
0 votes
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)

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.

What about your logic for merge sort ?

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

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.

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

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,385 answers
105,370 users