Python Insertion Sort Algorithm

A straightforward sorting technique known as “insertion sort” involves continuously inserting elements into the right places in an array that has been sorted. It operates by traversing an array repeatedly from left to right, sorting each element as it goes. It is easy-to-understand algorithm that performs well on small datasets.

How insertion sort work

1. Iterate from left to right through the array.
2. Compare each element to the ones before it and place it in the correct location in the sorted subarray.
3. It start from 1 and compare element — 1.
4. It will continue sorting until all components are sorted.

Image representation of insertion sort works

Insertion Sort

Steps to be done

1. First, you need to find the length of the array.
2. You should not forget that array elements are comparing with previous values, so the for loop should start with 1 to length of list, and then you need to use the while else loop for comparing array elements.
3. You need to swap if the array of x-1 is greater than the current array value; otherwise, you need not change the array position.
4. return value once sorted.

app.py

def ins_sort(aray):
    len_list = len(aray)
    for i in range(1, len_list):
        ref_value = aray[i]
        x = i
        while x>0 and aray[x-1] > ref_value:
            aray[x] = aray[x-1]
            x -= 1 
        else:
            aray[x] = ref_value
    return aray
aray=[6,5,3,1,2]
print("before sort ",aray)
hello=ins_sort(aray)
print("result sorted is ",hello)

result of app.py

before sort  [6, 5, 3, 1, 2]
result sorted is  [1, 2, 3, 5, 6]

Follow for more interesting topics :-)