Hacker News Reader

Comment by mattferderer | Hacker News Reader

I agree that learning algorithms is underrated & helps you out with many aspects in life. I can't tell you how often I'm sorting something with someone (like Christmas ornaments) and want to explain the fastest route to sorting them.

I don't believe those books are all common sense though. They capture excellent ideas on working with your team, managing projects & writing your code in a way that is easy for people to understand months & years later. Those skills make up the majority of a lot of developers days. They're also not that common.

-Edit - I can't recall any of those books discussing patterns, which the post author mentions a few times are worth learning. I would highly agree in the value of learning patterns. One of the many patterns books for sure should be mentioned.

View on HN

> I can't tell you how often I'm sorting something with someone (like Christmas ornaments) and want to explain the fastest route to sorting them.

I'm imagining you using quicksort to sort ornaments, but then I started thinking that sorting algorithms aren't as helpful in real life as they are with computers because your brain can comprehend "the big picture" and do precision swaps or innovative transformations that a computer wouldn't know to do.

For example, say you need to slide some wooden blocks into a long slender box. The blocks have letters of the alphabet on them, and you want to load them such that z is in the very bottom and a it at the very top. You arrive at the table and you see the blocks are sorted - but in the reverse order. You could use a sorting algorithm to optimally correct this, or you could just flip the box over and load from the other side...

Given that the constant factors are so much larger and the number of items relatively small, we're unlikely to start really hitting the theoretical asymptotic complexities of sorting algorithms in these scenarios. But for what it's worth, like much real-world data, this sounds like a good fit for Timsort: https://en.wikipedia.org/wiki/Timsort It probably benefits from having a lot more sequential access than random access; the physical world is even more punishing than a processor cache.

Timsort is interesting. I had first read about it some years ago, maybe in the Python Cookbook, 2nd Edition (recommended, BTW, as is Edition 3). It's a hybrid and adaptive sort.

From the parent's Wikipedia link:

[ Timsort has been Python's standard sorting algorithm since version 2.3. It is also used to sort arrays of non-primitive type in Java SE 7,[4] on the Android platform,[5] and in GNU Octave.[6] ]

https://en.wikipedia.org/wiki/Tim_Peters_(software_engineer)

From the above Wikipedia link:

[ Peters also wrote the Zen of Python, intended as a statement of Python's design philosophy, which was incorporated into the official Python literature as Python Enhancement Proposal 20 and in the Python interpreter as an easter egg.[8] He contributed the chapter on algorithms to the Python Cookbook[9]. From 2001 to 2014 he was active as a member of the Python Software Foundation's board of directors. Peters was an influential contributor to Python mailing lists.[10] He is also a highly-ranked contributor to Stack Overflow, mostly for answers relating to Python.[11][7] ]

My favorite solution like this I saw was from grading an Algorithms class.

The assignment was "turn this min-heap implementation into a max-heap implementation". The correct solution was to flip the tests correctly.

The solution I liked the best just negated all the values as they came in, and negated them again as they came out, so as long as you were inserting numeric values, everything worked out! It was a) delightful and b) totally missing the point of the assignment, so I felt bad about marking it down, but the point was to demonstrate knowledge of heaps, and the proposed solution would have worked whether the internals were a heap or not.

> I can't tell you how often I'm sorting something with someone (like Christmas ornaments)

Do Christmas ornaments have a natural ordering?

I just put them in a heap.

I assume they’re sorted in ascending order of merriment.

I can't recall the last time I've ever had to sort christmas ornaments.

And if you did, I imagine you could perform the task just fine without advanced knowledge of sorting algorithms.

I find the idea that the OP’s computer science background was a “help” hilarious. I’m sure those he was helping sort Christmas decorations with are all wondering how they ever managed to do it in the past, alone, without the Christmas miracle of sorting algorithms...

It makes me wonder what the most practical sorting algorithm for sorting things by hand is- like, if someone tossed a 1000-page hand-written (but numbered) manuscript in the air, which algorithm would be fastest to sort them by hand? Card sorters used radix sort, but if you don't have a card sorting machine, maybe mergesort.

According to Algorithms To Live By (great book), libraries use a sort of merge sort.

Someone on HN mentioned the 'magic of ____ arrays' or something like that where search, insertion, merge, etc. were all constant time operations...

Ah! Clojure's persistent vectors: https://hypirion.com/musings/understanding-persistent-vector...

I would use stacks to sort. The book was about 1000 pages? I'll do about 10 stacks. Then figuring out which stack to put a given page in is fast. (Abstract this and you wind up with a binary tree, which is what made me think of the persistent vectors above.)

The correct sort for that situation is a most-significant-digit-first variant of a radix sort. Arrange the documents into 10 piles based on hundreds digit. Pile up all of them except the zeroes, then sort the zeroes recursively. Then pull the next segment out of the pile, and sort it recursively. And so on.

This is often the most efficient way to sort physical items when you have a constrained range and working space, without custom equipment.

And yes, it really helps to know about variants like the American Flag Sort to realize that you can mix and match algorithm properties. AFS is an in-place sort, which is horribly inefficient for physical objects, but the observation that you can do a radix sort in MSD order is a refreshing additional observation vs "radix sort is always LSD first" the way card sorters work.

Some of my friends are postal workers and have described their mail sorting to be roughly this. It's not a general algorithm though, there is knowledge of their route weaved in. So the most significant bit would be the street name, but they'd remember houses 42+ are earlier in the route and direct them to a different bucket. For this reason the person delivering the mail also sorts it.

Computer science isn't directly applicable because we generally deal with general purpose algorithms, but I wonder how often their work is applicable to us, how often could we see huge improvements by using a specialized for the purpose sorting algorithm?

Can’t tell if OP was being sarcastic or not

Ah, you and your fancy non-OCD brain.

I can't remember the last time I've sorted anything with an algorithm written by me. Last time I did that in AI class in College. :\

I just don't see a reason to spend excessive time optimizing, unless performance becomes an issue.

I have a set of ornaments of the twelve days of Christmas. Last year I sorted them into order so that I could easily make sure that they were in ascending order on the tree. I'm going to do the same thing in two days time when we put our tree up again. I'll admit that I did it by eye, putting 1 and 12 at opposite ends of a table and then slotting the others into what seemed like the right places.

Reply on news.ycombinator.com