Cognitame

'There are dangers to radical self-awareness and honesty. People will hurt you. People won't care that they've hurt you. People will justify hurting you. People will think that hurting you made them a victim of your reaction. People might expect thanks that they've hurt you and caused you to grow so strong.' -M.K. Lords

Insertion Sort

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

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 (>).