Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Which sorting algorithm should I use in this scenario?

A researcher has a database of 100 million records of people. The researcher wants to study the distribution of given names according to other criteria such as zodiac sign, birth year, etc, so wants to sort by name with the option of further sorting later.

Which sort should I use?

A. selection
B. quick
C. heap
D. insertion
E. merge

Thanks!

like image 345
thatbennyguy Avatar asked Oct 17 '25 11:10

thatbennyguy


2 Answers

It's not really my answer since you reached it yourself, but here it is for better visibility:

  1. Selection and insertion can be ruled out because they have O(n^2) average running time, which isn't going to cut it for 100M items.
  2. Heapsort and quicksort are ruled out because they are not stable. This problem needs a stable sort because the problem definition implies that when sorting further, the original order (by name) needs to be maintained.
  3. This only leaves mergesort as a suitable candidate.

Update: Exam-related advice

I have to admit that point 2 above (preserve the sort by name) is not totally clear from the problem description. However, this is an exam question and there has to be some way of trimming the options down to one. This is only made possible by demanding a stable sort, so the requirement is there even if the wording is not ironclad.

This way of practical thinking makes it IMHO much easier to reach definitive answers for some types of exam questions.

like image 54
Jon Avatar answered Oct 19 '25 02:10

Jon


Try mapping your requirements to the comparison table at http://en.wikipedia.org/wiki/Sort_algorithms#Comparison_of_algorithms.

like image 36
Oliver Charlesworth Avatar answered Oct 19 '25 00:10

Oliver Charlesworth



Donate For Us

If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!