4

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!

Improve this question
10
  • 3
    The key to the answer starts from the "option to further sort later" part. This implies that the second (or third or fourth) sort should respect the order that the first sort already imposed for items that the second sort considers equal. What does this tell you? Also, there are some sorts that can be ruled out immediately from the "100 million" part (another way to say "more than you want to know" -- the exact number doesn't play a role). Commented Jun 22, 2011 at 11:30
  • Ah, adaptability! Thank you very much Jon! :) Commented Jun 22, 2011 at 11:32
  • 2
    @thatbennyguy: No, not adaptability. Adaptability refers to the capability of an algorithm to sort faster if the input is already sorted "in some degree". This only applies if we are talking about the same sort criterion -- here you are asked to further sort with a different criterion. Commented Jun 22, 2011 at 11:35
  • 2
    @thatbennyguy: Anyhow, start from the low-hanging fruit. Which two answers can be immediately ruled out and why? Commented Jun 22, 2011 at 11:36
  • 1
    @thatbennyguy: Correct, but the reasoning is not 100% perfect. Selection and insertion can be ruled out because they have O(n*n) average running time, which isn't going to cut it for 100M items. Then heapsort and quicksort are ruled out because they are not stable (no such thing as "kinda" unstable). That only leaves merge. Well done! :) Commented Jun 22, 2011 at 11:46

5 Answers 5

Reset to default
6

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

When all else fails, use merge sort ;) Thanks for helping me find the answer instead of giving it yourself. It's always better that way :)
@jon....clear my doubt also.....why not radix sort???i mean what is the problem in using that???
@AbhimanyuSrivastava: The main problem is that there is no option F in the question. Further problems are that radix sort requires a bitwise representation of its input, and you would need to make a new representation for each field they ask you to sort by (you don't know that in advance). This would require extra space and make the sort O(n) at best in practice, which means it won't be fast enough. Also, making radix sort stable requires even more extra space.
Radix sort is terrible on strings unless they're of fixed short length.
4

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

Improve this answer

2 Comments

D'oh! This is a past exam question. They're supposed to have straight-forward answers, right? :S
@thatbennyguy: The question does have a very straightforward answer. You can answer it and justify the answer in three sentences at most.
1

Someone posted a duplicate, and this was going to be my answer. Since I went through the effort to type all this, I may as well share it for future readers.

Each sorting algorithm has its best and worse use cases. This is how I try to think about it:

  • Selection Sort: I rarely / never use selection sort because almost always insertion sort out performs it. This is best on small data sets and nearly sorted lists
  • Quick Sort: Looking for the best average case senario
  • Heap Sort: Best possible worst case
  • Insertion Sort: (See Selection)
  • Merge sort: Merge sort is slightly slower than quick sort but has guaranteed O(n log n) behavior. The key point here is that merge sort is much more stable than quick sort.

Obviously that is a very breif overview. You can find a lot more info on Wikipedia and through a Google search like: "When to use [Insert Algorithm Here]"

Hope that helps!

Improve this answer

2 Comments

Merge sort's performance is not at all like quicksort: it's slightly slower on average in most circumstances, but it has guaranteed O(N*log(N)) behavior, unlike quicksort. And, here, it's very relevant that merge sort is stable and quicksort isn't.
A sorting algorithm means that if the data contains equal entries, they remain in the same order. Stability is an absolute property, it doesn't make sense to say that an algorithm is “more stable” than another. Read the Wikipedia article. I recommend reading further as well.
0

If you want to get a histogram, I wouldn't sort the data. I would just go through all the data counting all the combinations of interest. This is an O(N) operation.

Sorting the data first is unlikely to improve speed. This is an O(N*log(N)) operation.

If wanted to sort all the record, I would use a Collection.sort() with a custom comparator which has all the fields you need to compare. You would have to load all the records into memory which will take a few GB, but once you have done this it should be pretty fast.

The only way to make this faster would be to filter down the criteria. If you do this, I would create a Collection which has a copy of the records of interest and sort that.

Improve this answer

Comments

0

The most efficient sorting algorithm, wouldn't be a traditional one.

Since you are sorting based on criteria such as birth year and zodiac sign, I would do a "stack sort" (I just made that up).

It would work this way.

Create a data structure for each possible sorted value. Let's use birth year for example. In birth year, there are only going to be ~100 different values that it could be.

  1. Declare a data structure for each possible value for Birth year (100 pointer arrays, one for each year)
  2. Loop through each record, and place a pointer to the record in that array.

When you're done looping through each record, you've now got 100 arrays, each filled with records that have that particular birth year. The great part about this is that you've done it in O(n) time, so it's much faster than any other sorting algorithm. This also works for zodiac signs etc...

Think outside of the box. This approach is very useful when sorting a large dataset (n) with possible values (m), where m << n.

Improve this answer

2 Comments

This is called a counting sort.
Thanks, I wasn't aware it had a name.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.