Cognitame

'I was now getting, as I have said, one dollar and fifty cents per day. I contracted for it; I earned it; it was paid to me; it was rightfully my own; yet, upon each returning Saturday night, I was compelled to deliver every cent of that money to Master Hugh. And why? Not because he earned it,—not because he had any hand in earning it,—not because I owed it to him,—nor because he possessed the slightest shadow of a right to it; but solely because he had the power to compel me to give it up. The right of the grim-visaged pirate upon the high seas is exactly the same.' -Frederick Douglass, Narrative of the Life of Frederick Douglass

# Insertion Sort

by Ethan Glover, Sun, Oct 12, 2014 - (Edited) Sun, Oct 12, 2014

• Line 2: Starts the for loop at the second element in the array and moves through entire array.
• Line 3: Set the key, the item to be sorted to a[j]
• Line 5: Set i to the next lowest element, the for loop starts at the second item, i starts with the first.
• Line 6: While i > -1 (ie. between a[0] - a[a.length] AND greater than the key. (ie. a[j]), move through the loop.
• Line 7: Copies a[i] to a[i+1] if a[i] is greater than the Key.
• LIne 8: Subtracts i by 1, and continues while loop until the beginning of the array.
• Line 9: When this copy process is over set the key to a[i+1], or the greatest number that the key is larger than.

Tracing this program can be a little complex. But basically if a(i) is greater than the key, it copies a(i) to where the key is while saving the key in it's own variable. The program continues to do this backwards, shifting the array to the right as far as it needs. Once that is complete the key is inserted into the proper spot.

If we have the array [5, 2, 4, 6, 1, 3] a step by step tracing should reveal the following pattern.

First while loop:

[5, 5, 4, 6, 1, 3] (Notice how the key 2 is temporarily gone from the array.)
[2, 5, 4, 6, 1 , 3]

Second:

[2, 5, 5, 6, 1, 3]
[2, 4, 5, 6, 1, 3]
[2, 4, 5, 6, 1, 3]
[2, 4, 5, 6, 6, 3]
[2, 4, 4, 5, 6, 3]
[2, 2, 4, 5, 6, 3]
[1, 2, 4, 5, 6, 3]
[1, 2, 4, 5, 6, 6]
[1, 2, 4, 5, 5, 6]
[1, 2, 4, 4, 5, 6]
[1, 2, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]

Note: To change the algorithm from increasing to decreasing order, all you have to change comparison operator on line 6 between a(i) and "key" to less than (<) from greater than (>).