Joel Watson
Joel.Watson92@gmail.com | LinkedIn: /in/joel3rbear | Twitter: @Joel3rBear
Project maintained by JoelMWatson Hosted on GitHub Pages — Theme by mattgraham
Home » Blogs » Insertion Sort Walkthrough
Stepping Through Insertion Sort
Using the the input array [8,4,23,42,16,15], we will be going through the pseudocode bewlow showing the the output at each step.
First we start with i at position 2 (index 1) of the array and j at postion 1 (index 0). We take the value at position i (4), store it in the temp variable, and compare it to the value in position j (8).
While j is greater than or equal to 0 and temp is less than the value at position j, the value at positon j is moved forward one postion, j is decremented, and the while statement conditions are checked again before repeating.
Once the while statement conditions fail, the temp will be set in the postion j + 1 and the output is array [4,8,23,42,16,15]
For step two we move forward to position 3 (index 2) for i and position 2 (index 1) for j. Set the temp to the value at i (23).
This time, since temp is larger than the value at array[j], we immediately break out of the while loop.
The temp is now set in the postion j + 1 and the output is array [4,8,23,42,16,15]
For step three we move forward to position 4 (index 3) for i and position 3 (index 2) for j. Set the temp to the value at i (42).
Again, like with step two, temp is larger than the value at array[j] so we immediately break out of the while loop.
The temp is now set in the postion j + 1 and the output is array [4,8,23,42,16,15]
For step four we move forward to position 5 (index 4) for i and position 4 (index 3) for j. Set the temp to the value at i (16).
This time, we move through our while loop twice to move the element to the left 2 spaces.
Once the while statement conditions fail, the temp will be set in the postion j + 1 and the output is array [4,8,16,23,42,15]
For step four we move forward to position 6 (index 5) for i and position 5 (index 4) for j. Set the temp to the value at i (15). We know this is the last step because we have reached the end of the array.
This time, we move through our while loop 3 times to move the element to the left 3 spaces.
Once the while statement conditions fail, the temp will be set in the postion j + 1 and the final output is the sorted array [4,8,23,42,16,15]
