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).
As we can see above, each iteration examines a subarray increasing in size, while it makes backwards checks starting from the checkpoint.
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
The code in Java is available at the Algorithms (Sedgwick, Wayne) booksite.
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”.