Insertion Sort and a Romanian folk dance

My previous posts dealt with some Project Euler problems and their algorithmic solutions.

So far I was real fuzzy when it came to talking about the performance of these algorithms. So I decided to do something about it.

I picked “The Pragmatic Programmer” from my book shelf and read through chapter 6/32 “Algorithm Speed”, roughly seven pages about the basics of estimating algorithms, the O() notation, common sense estimation and algorithm speed in practice.

This chapter also includes a chart, that shows the O() notations for various algorithms like traveling salesman or selection sort.

Down the rabbit hole I go….

I decided to do some reading and writing about sorting algorithms, starting with insertion sort.

Pseudocode

Here is a pseudocode representation of insertion sort on a zero-based list:

selection_sort_pseudocode

The algorithm consists of an outer for-loop and an inner while-loop.
The for-loop iterates over all elements in the list to be sorted starting with the second element.

Why starting with second element and not the first one? Because the assumption is that the first list element is already sorted by default.

The inner-while loop does the actual comparison of list elements and swapping if necessary.

Example

Let’s take a zero-based list A of six integers. length(A) = 6:

insertion_sort_1

The algorithm’s for-loop iterates over the list elements from A[1] to A[5].
length(A – 1) = 5:

insertion_sort_2

The current position is stored in the variable j.

Now, while the value of j is greater than 0 AND the value of A[j-1] is greater than the value of A[j], the elements A[j-1] and A[j] get swapped and the value of j is decreased by 1.

This is the algorithm’s first iteration:

i = 1;
j
= 1;
j > 0 true;
A[j-1] = A[1-1]A[0] = 5;
A[j] = A[1] = 3;
A[j-1] A[j] = 5 > 3 → true;

Therefore swap A[j] = 3 with A[j-1] = 5.

j = j – 1 = 1 – 1 = 0;

And that is list A after the first swap:insertion_sort_3As j = 0 > 0 false, we do not enter the while-loop another time but continue with the for-loop.

= 2;
j
 = 2;
j > 0 true;
A[j-1] = A[2-1] = A[1] = 5;
A[j] = A[2] = 7;
A[j-1] A[j] = 5 > 7 → false;

Again we do not enter the while-loop, but continue with the for loop.

i = 3;
j = 3;

The for-loop moves through the list from left to right, the while-loop backwards.

This is the complete sorting sequence:

insertion_sort_4

Some Java

Let’s implement the algorithm in Java.insertion_sort_java

A Romanian folk dance

By the way, I came across this video on Youtube, that teaches the workings of insertion sort, which is pure genius:

So far so good. But what about performance? No answer yet. And I don’t want to simply copy Wikipedia. So I will have to do some reading first.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s