I am studying up for a pretty important interview tomorrow and there is one thing that I have a great deal of trouble with: Sorting algorithms and BigO efficiencies.
What number is important to know? The best, worst, or average efficiency?
+3
A:
worst, followed by average. be aware of the real-world impact of the so-called "hidden constants" too - for instance, the classic quicksort algorithm is O(n^2) in the worst case, and O(n log n) on average, whereas mergesort is O(n log n) in the worst case, but quicksort will outperform mergesort in practice.
Martin DeMello
2009-09-13 17:02:51
Natural Mergesort can leave quicksort and quickersort in the dust -- cfr http://svn.python.org/projects/python/trunk/Objects/listsort.txt, http://stackoverflow.com/questions/154504/is-timsort-general-purpose-or-python-specific, http://www.hatfulofhollow.com/posts/code/timsort/, etc, etc.
Alex Martelli
2009-09-13 17:13:30
While this is a great answer, I must admin I'd be hesitant to hire someone who didn't understand something so basic and obvious as a developer.
DVK
2009-09-13 17:17:56
DVK, you are sounding like an ivory tower kind of guy, the kind of person who jealously guards his small area of knowledge with the greatest amount of effort. Are you not here to share your knowledge, and your effort to support community? Are you fearful that someone will gain competency in this area and then take your job?
MedicineMan
2009-09-13 18:05:43
alex: that's pretty neat. wasn't aware of just how good timsort was.
Martin DeMello
2009-09-13 19:43:00
@MedicineMan. Your response to @DVK was a little too defensive. There are some good companies out there who completely agree with DVK - this is Paint The Fence stuff.
jamesh
2009-09-14 11:26:59
+2
A:
All of them are important to know, of course. You have to understand the benefits of one sort algorithm in the average case can become a terrible deficit in the worst case, or the worst case isn't that bad, but the best case isn't that good, and it only works well on unsorted data, etc.
Ed Marty
2009-09-13 17:03:56
+1
A:
I recommend that you don't merely memorize these factoids. Learn why they are what they are. If I was interviewing you, I would make sure to ask questions that show my you understand how to analyze an algorithm, not just can spit back out something you saw on a webpage or in a book. Additionally, the day before an interview is not the time to be doing this studying.
I wish you the best of luck!! Please report back in a comment how it went!
San Jacinto
2009-09-13 17:14:03
thanks, memorization is never the best route, but when faced with a deadline, I need to prioritize what goes in the brain first.
MedicineMan
2009-09-13 18:06:57
+1
A:
In short.
Sorting algorithm efficiency will vary on input data and task.
- sorting max speed, that can be archived is n*log(n)
- if data contains sorted sub data, max speed can be better then n*log(n)
- if data consists of duplicates, sorting can be done in near linear time
- most of sorting algorithms have their uses
Most of quick sort variants have its average case also n*log(n), but thy are usually faster then other not heavily optimized algorithms. It is faster when it is not stable, but stable variants are only a fraction slower. Main problem is worst case. Best casual fix is Introsort.
Most of merge sort variants have its best, average and worst case fixed to n*log(n). It is stable and relatively easy to scale up. BUT it needs a binary tree (or its emulation) with relative to the size of total items. Main problem is memory. Best casual fix is timsort.
Sorting algorithms vary also by size of input. I can make a newbie claim, that over 10T size data input, there is no match for merge sort variants.
Margus
2009-09-13 18:27:45
answer doesn't address the central question posted, but it does present valuable insight into various sort performances based on real world experience.
MedicineMan
2009-09-13 18:33:47
A:
You may also want to look into other types of sorting that can be used when certain conditions exist. For example, consider Radix sort. http://en.wikipedia.org/wiki/Radix%5Fsort
ldog
2009-09-14 01:00:51
+1
A:
I am over with one set of interviews at my college just now...
Every algorithm has its benefits, otherwise it wont exist. So, its better to understand what is so good with the algorithm that you are studying. Where does it do well? How can it be improved?
I guess you'll automatically need to read various efficiency notations when you do this. Mind the worst case, and pay attention to the average case, best cases are rare.
All the best for your interview.
Lazer
2009-09-14 16:33:57