2 min read
Insertion Sort Using Python
Last Update: 23 September, 2022Insertion sort is one of the simple sorting algorithms that can work very well on relatively smaller lists (or arrays). It performs better in arrays that are partially sorted already, as it doesn't need to fire a second iteration. We are going to see the reason why right away.
Ok, so basically we are comparing two adjacent values and swapping them if they are in the wrong order. This will help us get carry the current lowest to the start of the list (in a max sort).
§An Example to Help Us Understand
Our first iteration will fire array / list size minus one times. Our second loop will fire when the current value need to be swapped with the adjacent value. If the swap is necessary in the next execution of the second loop we look for the need of swap again in the values one index left of the previous one. This way we push the lowest value to the front in each iteration. This logic is close to how we would actually sort gaming cards in our hands right?
def insertionsort(arr, size):
for i in range(1, size):
j = i-1
while j>=0 and arr[i] < arr[j]:
arr[j], arr[i] = arr[i], arr[j]
j -= 1
i -= 1
array = [5,4,6,8,2,7,1]
sz = len(array)
insertionsort(array, sz)
print(array)
I think going step by step on this example will help us a lot.
When the second loop starts, we start with the i=1 and j=0. Then we check if we are in the array's bounds. If so we start the while loop. if arr[i] is smaller than arr[j] (if left is larger than right) we swap and lower decrement i and j by one to check the two values one index left. So ath at the end of the first iteration of the second loop our array looks like this:
[4, 5, 6, 8, 2, 7, 1]
As you can see we swapped 4 and 5 and we don't have anything on the left so we stop. We start the second execution of the first iteration with i=2 and j=1. There is no need for swapping so we move on. No need to swap in the third execution neither.
In the fourth execution of the first iteration j=3 and i=4. After the first swap (2 and 8) :
[4, 5, 6, 2, 8, 7, 1]
Now we decrement i and j and check again. Another swap is needed and the result is (6 and 2 are swapped):
[4, 5, 2, 6, 8, 7, 1]
I assume you got the logic of it so we won't go explaining every step as. It would make this post too much longer than it's supposed to be. We continue to execute the while loop until the 2 is the first value of our array. We will keep "selecting" the lowest and pushing it to the front until we have a sorted array.
§Complexity of Selection Sort
Selection sort is not very time efficient with a nested loop inside an iteration with the time complexity of O(N²). But it's really efficient in space as we don't need to keep a hefty auxuliary array to keep our values or anything. Space complexity of selection sort is O(1). So consider it next time you have the time but not the space.
Keep on learning!
Ilker AkbiyikTable of Contents
Related Posts
