Earlier quoted context omitted.
You can pry my stable sort algorithms out of my cold, dead hands.
Add the factors to the sort key? Every sort is stable if you have some vague ideas about what to sort on.
What?
Sorting Algorithm Cheat Sheet
41–50 of 52 posts
Re: Sorting Algorithm Cheat Sheet
#42Earlier quoted context omitted.
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.
As someone who has spend a great deal of time on sorting algorithms when I was in academia ( even published one) I completely agree with this sentiment. Sorting algorithms are tricky to get right and there is a lot of edge cases, so even when you (think) you know what you are doing you still get it wrong. Been there many times and it always causes some frustration.
Do you really want your business critical sorting rely on something that only might work?
Sorting algorithms are like crypto, don't roll your own if you can avoid it.
Re: Sorting Algorithm Cheat Sheet
#43Earlier quoted context omitted.
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.
For a problem i faced I ended up being able to produce very small chunks of already sorted data and using the merge part of the stable sort algorithm (it was provided).
Not only that, I ended up being able to do it lazily making the user experience much better.
Re: Sorting Algorithm Cheat Sheet
#44Who 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).
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.
Dev with decades of experience here - I've worked with a variety of languages and platforms, and across different domains. I'm not sure I've ever had to implement a sorting algorithm, or even had sorting as an optimisation issue (and I love micro-optimisation, a bit too much TBH!). I've had to sort things, of course, but standard (or at least "common") libraries invariably have sorting functions built-in.
Re: Sorting Algorithm Cheat Sheet
#45There is also sorting networks. If you have to sort short list of items, it's probably the best solution around.
Re: Sorting Algorithm Cheat Sheet
#46Curious: 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?)
The links to decent writeups with example code (
excellent to have) are a nice surprise when a row is expanded.
On my firefox browser the paragraphs and elements in the table and writeups are somewhat excessively spaced vertically.
Re: Sorting Algorithm Cheat Sheet
#47Earlier quoted context omitted.
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.
And this is why O() notation drops constants. 0(bits) or O(bits/8) aka bytes are the same thing. It's also worth pointing out that in standard comparison sorts, the comparison itself is technically linear to radix too, but is treated as constant. I get why it's dropped but it's worth knowing.
Re: Sorting Algorithm Cheat Sheet
#48Who 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).
Some people like that sort of thing. Mostly the "academic" types. The memorizers. There are people who got through their higher education by using memory instead of wit. I know some of those people, I went to school with some of them, they were always studying and ramming as much "data" into their brains as possible... while I was getting through with minimum of effort by just coding a lot and trying to think about t…
This has to be the most misguided attitude that you can have. I don't think this will serve you well in your career.
Re: Sorting Algorithm Cheat Sheet
#49Earlier quoted context omitted.
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.
For a problem i faced I ended up being able to produce very small chunks of already sorted data and using the merge part of the stable sort algorithm (it was provided). Not only that, I ended up being able to do it lazily making the user experience much better.
And I have been forced to write sorting algorithms from scratch as well. But it was truly a last resort. In my case I had to work with data that literally did not fit in uncompressed form on the computer that I had to work with. So I had to write a disk sort where data as kept in compressed form. (I used merge sort for this.)
However the fact that sometimes we are forced to our last resort doesn't change the fact that we should be aware that it really is a last resort.
Re: Sorting Algorithm Cheat Sheet
#50Earlier quoted context omitted.
If you have a theoretical computer with single-bit registers, sure. Quicksort is also quite slow on such an computer.
And this is why O() notation drops constants. 0(bits) or O(bits/8) aka bytes are the same thing. It's also worth pointing out that in standard comparison sorts, the comparison itself is technically linear to radix too, but is treated as constant. I get why it's dropped but it's worth knowing.
Exactly. You can try to compare two bytes, but really you are comparing 8 bits, if you thought about it algorithmically. Maybe those steps are 100% parallel. But it's irrelevant to the big O. You are measuring number of steps, and it's intended to be hardware independent.