Harder, Better, Faster, Stronger

submited by

Style Pass

2021-07-25 16:30:05

In Tunnels of Doom!, I wrote that the disjoint sets algorithm is one of the very few algorithms every programmer should know. That got me thinking. Should? What about must? If everyone must know about disjoint sets, what other algorithms must every programmer know about?

Understanding these data structures and what trade-offs are involved will help you choose wisely which will suit your application better. Note that the structures that equalize depth do not only make sure that the worst case is the average case: they implicitly suppose that all items in the collection have an equal probability of being accessed—something quite contrary to the Pareto Principle (or more accurately, maybe, to Zipf’s law).

QuickSort is a comparison-based sort, that is, elements are compared to each other to determine their relative order. Eventually, QuickSort makes enough comparisons ( for items, on average, but has a worst case of —which can be avoided, but that’s another story for now) to eventually produce a sorted list of items. The theoretical lower bound for comparison-based sorts is comparisons, so QuickSort is doing very well on average. The great simplicity of the algorithm makes it very interesting in a very wide range of cases.

Radix sort, on the other hand, an address transformation sort that sorts the items in linear time, that is, in , making it much faster than QuickSort. It is much faster, but Radix Sort is much simpler when keys are numeric or of fixed width; dealing with variable length keys efficiently makes the algorithm slightly more complex. Read more on Radix Sort here and in this old DDJ article.