A Software Engineering Space

IntroSort: Quicksort with a parachute

In a previous article on quicksort, I called it a fast sorting algorithm with an achilles heal: for certain inputs quicksort slows waaaaaay down. This is quite unfortunate, because on most inputs quicksort is very fast. A lot of research has gone into improving quicksorts worst case performance, the majority of it focusing on the […]

Implementing C++ Iterators in Binary Search Trees

My past two articles dealt with deleting items from an AVL tree in C++ and linked list iterators in java. So I figured I would let the two paths cross in this article by covering forward iterators for AVL trees using the STL style of the iterator pattern. If you haven’t ready my previous two […]

Iterative AVL Trees – Deletion

In a previous article I introduced what AVL trees are, their structure and insertion. If you have not read that article, go back and read it first, as code in this article builds off of code from there. AVL Tree’s are the original self balancing binary search tree, and as with all binary search tree’s […]

Design Patterns: The Iterator Pattern

Object oriented program strives to decouple a classes implementation from its functionality. In brief, a List could be implemented using an array, a linked list, a binary search tree, or a hashtable, and function in the same way. This is effectively managed through the use of interfaces. But if a class is a container, and […]