Resolved: Issues with the example that was taken for explaining Insertion sort
In the example that you shared, initial list was 3,2,7,5,15,9,12 and applying the insertion short we arrive at 2,3,5,7,9,12,15 which is alright, however, had the initial list been: 3,2,7,1,15,9,12 - the method wont's work:
Steps: 3,2,7,1,15,9,12 -> 2,3,7,1,15,9,12 -> 2,3,1,7,15,9,12 -> 2,3,1,7,9,15,12 -> 2,3,1,7,9,12,15 [one is still misplaced]
Hey Saurabh,
Thank you for your question!
Remember that insertion sort assumes that the 'sublist' to the left of the current item remains sorted. Therefore:
3,2,7,1,15,9,12 -> {3 is the first number, so we don't do anything} ->3,2,7,1,15,9,12 -> {we sort the list to the left of 2} -> 2,3,7,1,15,9,12 -> {nothing changes} -> 2,3,7,1,15,9,12 -> {now we need to sort everything to the left of 1 (index i = 3)} -> 2,3,1,7,15,9,12 -> 2,1,3,7,15,9,12 -> 1,2,3,7,15,9,12 -> {now we continue where we left off (index i = 4)}
-> 1,2,3,7,15,9,12 -> 1,2,3,7,15,9,12 -> 1,2,3,7,9,15,12 -> {everything to the left of 9 is sorted, so we continue where we left off} -> 1,2,3,7,9,15,12 -> {everything to the left of 12 is sorted}
-> 1,2,3,7,9,15,12
I hope this helps! The code provided by Giles should enhance your understanding of the method.
Thank you and keep up the good work!
Kind regards,
365 Hristina
Thank you for the response Hristina and I agree, the code was perfect, it was more of an apprehension that I had around the example that was picked up, since, it looked fairly straightforward and didn't cover the nuance where no. to the right is even lower than the no. to the left of the index.