Whenever I create my yearly reading list, I need a way to order the books. Sure, I could just shuffle them normally, but that leads me to the temptation of cheating and re-shuffling them so that the books I want to read most are first. What I really need is a shuffle that will shuffle the same way every time.
Enter: hashsort
Yesterday’s post from Programming Praxis asks us to solve a problem known as the Dutch National Flag problem (attributed to Edsgar Dijkstra): sort an array of red, white and blue symbols so that all reds come together, followed by all whites, followed finally by all blues.
Yesterday’s post from Programming Praxis has us trying to find the predecessor and successor to a given value in a binary search tree. There are actually two general algorithms for doing this, depending on if you have parent pointers or not–but they’re asking for the algorithm without.
I did say in yesterday’s comments that I would try re-implementing splay heaps using an imperative model with an array (Scheme’s vector) as the back end rather than a functional one with trees. Well, here is is.
Yesterday’s post from Programming Praxis gives a new (or at least different) vantage point on one of the most common problems in Computer Science: sorting. Today, we’re going to implement a data structure known as a splay heap and use that to perform a heapsort.