Sorting Algorithms Studies: Insertion Sort

Explanation

This algorithm works by, starting at the second element of the list, repeatedly comparing the current value with the previous value, and swapping them if the previous value is higher than the current value; or, if the sorting is being done in decrescent order, if the previous value is lower than the current value. Having provided the clarifications, from now on this article will focus on the crescent order implementation.

Besides doing that with the previous element, if there was a swap, before going ahead and making the comparisons amongst the next elements, it goes retroactively, verifying if the swapped element is in the right place. If it isn’t, continues swapping it with the previous elements until it is. After that, the algorithm resumes the comparisons with the next elements.

Structure

It is comprised by two nested loops:

• The outer one loops amongst the numbers that comprise the range between 1 and the size of the array, minus 1. Example: if the array has size 5, the outer loop will loop from 1 to 4. Let’s call the number of the outer loop x.
• The inner loop is the one that actually makes the comparisons and swaps. It loops amongst the numbers that comprise the range between x and 0, not including zero itself. Let’s call the number of the inner loop y. But, although the loop is comprised by these values, an inner loop iteration will only be executed if the element in the y index is lower than the element in the y - 1 index. Example: if the array has size 5, the inner loop will loop from 2 to 0 on the first outer loop, 3 to 0 in the second outer loop, and so on, always checking the condition stated above.
• For each y in the inner loop, as the condition above was already checked as a requirement for the loop iteration to be valid, all that is left is to swap the element in the index y with the one in the index y - 1.

Also, there is an Insertion Sort implementation with a minor optimization. Instead of continuously swapping elements, for each outer loop, it stores the value of the element in the x index in an auxiliary variable. Then, it keeps assigning the value in the index y to the y + 1 index as long as y is bigger or equal to zero and the value in the index y is greater than the value in the auxiliary variable. Finally, when the inner loop is finished, the auxiliary variable value is assigned to the y + 1 index.

Code

This is the implementation of Insertion Sort in Python. It may look slighter more complex than the usual Insertion Sort implementation, but that’s because I’ll to provide codes that work both for the crescent and decrescent sorting.