You are required to sort a file containing integers between 0 and 999 999. You c

Question

You are required to sort a file containing integers between 0 and
999 999. You cannot afford to use one million pigeon-holes, so you decide instead
to use one thousand pigeon-holes numbered from 0 to 999. You begin the sort by
putting each integer into the pigeon-hole corresponding to its first three figures.
Next you use insertion sorting one thousand times to sort the contents of each
pigeon-hole separately, and finally you empty the pigeon-holes in order to obtain
a completely sorted sequence.
Would you expect this technique to be faster, slower or the same as simply using
insertion sorting on the whole sequence (a) on the average, and (b) in the worst
case? Justify your answers.

//algorithmics

Explanation / Answer

(a) Since the given numbers are sorted in a manner that there first three digits are sorted in some order so if we consider the average case of insertion sort the algorithm is going to perform better that it normally do, because we already known the fact that insertion sort take O(n) time if the array is almost sorted. so same can happen here and the result will may be obtained a bit faster using average case of insertion sort algorithm.

(b) If we talk about worst case scenario the sorted order on the basis of first three digit sorting will still be overall unsorted and is in complete reverse so the algorithm in such condition will take more time to solve the problem, in this scenario algorithm will take O(n2) at any point of time. Because if after arranging the numbers by using thier first and second digit strategy, there is a chance that the sorted numbers are still in c complete unsorted order taht is why in this condition the algorithm will take O(n2) to solve.

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.