feature request: make O(k) bright red, like O(n^2). As it stands, it looks nice and pleasant like O(1) but it's honkin' terrifying.
Sorting Algorithm Cheat Sheet
21–30 of 52 posts
Re: Sorting Algorithm Cheat Sheet
#22Who is still asking candidates to talk about sorting algorithms? It is just trivia and has little to no bearing on if the candidate can actually do the job (unless the job relates to the runtime of sorting algorithms, of course).
There are two situations where I wouldn't harass my coworkers for asking sort related questions.
One, I've asked. Not implementing sort, but implementing complex compare() functions for sortable values. There are many things I can accept as flaws in a coworker but inability to deal with 3 conditionals at once isn't one of them. And I've had people (interviewed or worse, worked with) who can't sort by last name, first name, age.
The other is the "I gave you code now tell me what's wrong with it" answer but that's not writing a sort algorithm, that's detecting that someone needs a better one.
Personally, I'd be all too happy if we stop interviewing people expecting answers that would never pass a code review. I'd say it's hypocritical but it's not even that. It's just wrong headed, and gives bad information to the candidate.
Re: Sorting Algorithm Cheat Sheet
#23Curious: did people notice that you can click on each algorithm and click the blue button to get a detailed write up of how it works? (Or is that too hard to find?)
Re: Sorting Algorithm Cheat Sheet
#24feature request: make O(k) bright red, like O(n^2). As it stands, it looks nice and pleasant like O(1) but it's honkin' terrifying.
Oh yeah, looks like we messed that up. That space complexity also doesn't even agree with the final space complexity we describe in the write up.
I'm gonna actually change the space complexity in the table for both counting sort and radix sort to O(n)--that at least matches the amount of hand-waviness we used for the time costs for those two in the table.
Re: Sorting Algorithm Cheat Sheet
#25[deleted]
Re: Sorting Algorithm Cheat Sheet
#26Best case for heapsort is actually O(n). Build heap always takes O(n). Then e.g. when all keys are the same, the max-heapify call will take O(1) instead of O(logn).
Hmmmm good point!
Re: Sorting Algorithm Cheat Sheet
#27Original author here, happy to answer questions about data structures, algorithms, and coding interviews!
It might be notable that on very small lists (up to around 50, maybe 100 depending on cpu/cache) insertion sort is fastest of all, even on difficult input distributions. Its so simple that cpu can skip through it rapidly. I noticed this myself and have also read other developers mention it in sort design discussions. A popular general purpose sort called 'Timsort' defaults to it for small sequences. Its possible to t…
One of the big factors behind this is that the cost of pipeline stalls in a theoretically good algorithm can significantly exceed the cost of extra comparisons.
Whether that is true depends on a combination of how much data you have, what kind of data you have, and your programming language's low-level representation.
For ints in C++ and a list of 20 elements, it will be reliably true. For strings in Perl with a list of 500 elements, it reliably won't be true.
Re: Sorting Algorithm Cheat Sheet
#28Of course in the real world for problems where sorting is actually the bottleneck and not just something you want not to kill your app's performance, you end up with things like timsort that destroy all these in practice.
I'd say it's the other way around: you use whatever your language provides as default (which is probably something like Timsort) until it becomes a bottleneck and then you analyse the data and write something that is specific to your use case that will blow Timsort out of the water. Timsort is your first choice.
In practice this boils down to, "you use whatever your language provides".
If sorting became a bottleneck, I'd literally look at every possible approach to speed it up that I could find before considering improving the sorting algorithm. Starting with trying to figure out how to throw around less data while trying to solve the problem.
Re: Sorting Algorithm Cheat Sheet
#29Earlier quoted context omitted.
Sorting is such a foundational problem in computer science that pretty much every job will end up relying on the runtime of sorting algorithms. Not every job requires being able to write a bulletproof dual-partition QuickSort, of course, but knowing complexity bounds is important, even if you’re just calling your standard library’s implementation: it places fundamental bounds on what things you can improve.
Pretty much every job? I'd say about 10%. With all the web and web-adjacent jobs around, maybe even less. Most stdlibs are already written in a sensible way, so calling "sort" usually means calling quicksort. Most people just do not care, they have tickets and bosses to worry about.
Absolutely. While every job will depend on sort, so many of them will have negligible benefit by changing the least efficient algorithm to the most.
And most of them just use a native language sort that does something relatively smart out of the box.
It's good to write all of these at don't point so you understand why things are inefficient.
Re: Sorting Algorithm Cheat Sheet
#30> Radix sort looks fast, with its O(n)O(n) worst-case time complexity. But, if you're using it to sort binary numbers, then there's a hidden constant factor that's usually 32 or 64 (depending on how many bits your numbers are). That's often way bigger than O(\lg(n))O(lg(n)), meaning radix sort tends to be slow in practice. The constant factor in radix sort isn't the number of bits, it's the number of digits. Since on…
It's the number of bits. You can change to bytes, but you are just hiding another constant factor of 8 by doing that.
If you have a theoretical computer with single-bit registers, sure. Quicksort is also quite slow on such an computer.