A Software Engineering Space

Counting Islands with Flood Fill

Sometimes when I’m bored I reach for one of the various books of programming challenges, flip to a random page and work through random problems until I’ve had enough. This past weekend I flipped to a random page and was greeted with the “Counting Islands” problem. The problem goes like this: “You are a provided […]

Of Humble Constructs: The Event Loop

Software development is like a 3d-jig saw puzzle. Small “pieces” – in the form of basic instructions – are used to construct larger pieces of increasing complexity, such as sub routines, functions, and objects. At differing levels of abstraction this can be anything from combining basic arithmetical operations with a stack to create a RPN […]

Insertion Sorting Linked Lists

In yesterdays post I covered implementing selection sort for linked lists, so I figured I would cover Insertion sorting linked lists for the sake of completeness. I ended the selection sort article with assertion that for the complexity of implementing it compared to the performance of the actual algorithm that you are much better off […]

Selection Sorting a Linked List

I’ve always liked the selection sort algorithm. I’m not sure why, I think it’s the frank simplicity of it. Unfortunately, it is amongst the slowest of sorting algorithms, and is firmly in the realm of theoretic interest over practical use. Yet still it is studied because it’s useful instruction for how to construct a more […]

Rotate, Reverse, Block Swap, Repeat.

I was reading through a paper about block merge sort and in the article was a list of helper functions that the algorithm utilizes during its execution. This list was kind of a “who’s who” of array manipulation algorithms. These algorithms are useful for a whole lot more than just block merge sort, and so […]

Lets Talk Selection

Often times when we have a collection of values, we are more interested in the order statistics of the collection: find the min value, find the max value, find the K’th smallest value, and what have you. There are a number of data structures that efficiently support these operations: a binary search tree can support find […]

Another look at heapifying

Heaps are ubiquitous in computer science. If you need the minimum, or maximum of a collection, few choices are better than a heap for getting them. Heap-forming algorithms are the foundation of many different algorithms and data structures. From heapsort to priority queues, to huffman coding, heaps really are everywhere. Heaps make use of two […]

Shellsort: A Sorting Enigma

For the first 15 years or so of computing if you wanted an in-place general purpose sorting algorithm you were stuck with O(n^2) sorting algorithms. Insertion sort, selection sort, and bubble sort were about as far as the art of sorting had gotten at the time. That’s not to say faster sorting methods were not […]