Insertion Sort

The very first algorithm that CLRS explains is Insertion Sort.

Before I get into that, I have to rant a little bit.

One of my gripes about CLRS is its pseudocode. In the 2nd edition, the Pascal-esque pseudocode is hard to understand (and subsequently refer to later) for Java developers with its unfamiliar arrows, triangles, random “do”s, etc. Thankfully, this was changed in the 3rd edition (but alas, I have the 2nd edition), where the pseudocode better resembles a C-style language like Java.

Even if the pseudocode is easier to understand, another issue is that it’s very close to actual code. Actual code is hard to remember. I believe that in order for us to be keep algorithms in our memory, we need to memorize the high-level thought process behind the algorithm itself. We can than construct the code from that point on. I’m in favor of a “Plain English Description”, and that is what I’ll include with each discussion of an algorithm I plan to write about.

Plain English Description

Start with the 2nd element of the array as the checkpoint. Compare the checkpoint with the numbers before it, and shift it to the left (as the minimum) of all numbers to the right of it. Increment the checkpoint and repeat the shifting process until the checkpoint reaches the end of the array (and all numbers are sorted).

image

Pseudocode

As we can see above, each iteration examines a subarray increasing in size, while it makes backwards checks starting from the checkpoint.

Pseudocode mnemonic

Increasing subarrays (at the upper limit) with backwards checks for shifting elements to the right.

For checkpoint = 1 to array.length 
    Set minimum to array[checkpoint]  
    Set shiftpoint to element before checkpoint 
    While shiftpoint > 0 and array[shiftpoint] > minimum 
        Set element after shiftpoint to array[shiftpoint] 
        Decrement shiftpoint 
    Set A[shiftpoint] to minimum

Code

The code in Java is available at the Algorithms (Sedgwick, Wayne) booksite.

Analysis

The best case occurs when the array is already sorted. This means the inner loops makes zero iterations every time, so the outer loops iterates n -1 times. The best case is Ω(n).
The worst case occurs when the array is in reverse sorted order. Each time the outer loop iterates, the inner loop iterates i - 1 times. The number of inner-loop iterations forms an arithmetic series:

1 + 2 + 3 + … + (n - 2) + (n - 1)

which evaluates to O(n2).
For the average case we assume that the inner loop iterates over half of the elements of the subarray. This means it would make (i - 1)/2 iterations, so the running time would be cut in half. However, asymptotically it’s not different from the worst-case running time as ½ is a constant factor.

Insertion sort compared to the other sorts is a good choice if the array is “almost-sorted”.

Further Reference

Tags: algorithms

Simplifying Nested Ternary Operators

Today I saw code like this in a JSP that used nested ternary operators:

<c:set var="formmethod" value="${ FooCondition ? 'POST' : BarCondition? 'POST' : BazCondition? 'POST' : 'GET'}"/>

Generally, using ternary operators in code is discouraged because it can be hard to read.  One exception is if you have a simple, concise expression like so:

number < 0 ? sign = "negative" : sign = "positive"

It can be understandable to use a ternary operator in a JSP since the JEE expression language is limited when it comes to operators.  However, there are a couple of ways to make that expression easier to understand.

One way is to use the <c:choose> tag. This would clarify things but add some verbosity.  A more concise way to simplify this expression is like so:

<c:set var="formmethod" value="${ FooCondition or BarCondition or BazCondition? 'POST' : 'GET'}" />

Isn’t that better?

Tags: jsp

Resources for Studying Data Structures and Algorithms

Introduction to Algorithms by Cormen, Leisersen, Rivest, Stein

image

This is considered the standard reference used in universities everywhere, referred to as “CLRS”.

You can find video lectures here:

MIT Fall ‘05 | MIT Spring ‘08 (notes) | MIT Fall ‘11

Notes:

MIT Spring ‘11 | Peteris Krumin’s notes

Algorithms (4th Edition) by Robert Sedgewick and Kevin Wayne

image

One of the key differences between this book and CLRS is that all of the code is in Java (and not just pseudo-code).  On top of that, the code exemplifies using Generics, implementing the interfaces from java.util, and other Java features.  It also provides “clients” to test the algorithm implementations.  This makes it a snap to convert it into production-ready code.

Another difference is that there is less of an emphasis on math and proofs, while there is a heavier emphasis on code.  With CLRS, one could say that it is light on code and heavier in math.

The book’s site is here, and there are very nice Coursera courses (part 1, part 2) based on it.

The Algorithm Design Manual by Steven Skiena

image

This book is highly recommended by Steve Yegge. It’s lauded especially because of its emphasis on real-world examples.  The example code is in C.

Algorithm Design by Jon Kleinberg and Éva Tardos

image


I don’t know much about this book, but it was suggested by Tom Cormen on Twitter as a supplement to CLRS.


Outside of books, there are some decent Algorithm tutorials at TopCoder, as well as some very nice video tutorials by Derek Banas at the NewThinkTank.  The videos total up to about 4.5 hours and they’re good for people who haven’t taken any class on Algorithms in college.

Atif

Back to Basics: Anatomy of a Java class

When working in the “real-world”, you are often going in and modifying existing code.  If you write something new, like a Java class, the IDE will often auto-insert some sort of template for you.

After years of doing this, you may forgot something as basic as how to write a simple “hello world” in the language you claim to be proficient with!

It’s good to go “Back to Basics” and re-learn how to do it:

public class MyClass{
    public static void main (String[] args) {
        System.out.print("Hello world!");
    }
}

Another good reason to learn this is, if you take a break from a “Big Ol’ IDE” and just hack it in VIM or Emacs.  This is one of the advice from the book The Pragmatic Programmer: to try writing in a different environment than you are used to.

But that’s a post for another time.

Tags: java basics