Insertion Sort in python

 In Insertion Sort , we sort the element in a list by taking 1 element at at a time and placing it in a position of sorted order.

For eg , let a list be [45,23,56,8,34]

In step 1 the first two elements will be compared and arranged accordingly .

Then in step 2 the third element will be compared with the first two elements and inserted to create an order (ascending or descending) among the three elements and this process will be continued until all the elements have been arranged.

CODE:

l1=list()

n=int(input("Enter the number of elements in list: "))

for e in range(n):

    ele=int(input("Enter value for element: "))

    l1.append(ele)

print("Original list :",l1)

for i in range (1,n):

#in the outer loop it will traverse through each index from 1 till the last

    for j in range(0,i):

# in 2nd loop each element will be compared with every element before it

        if l1[i]<l1[j]:

            l1[i],l1[j]=l1[j],l1[i]

# if current element is smaller than any previous element

# then it would be shifted back

            print(f"changing place of {l1[i]} and {l1[j]}: ")

            print(l1)

    print(f"Sorted till index {i}")

print("Final sorted list: ")

print(l1)

NOTE: All the print statement are just for explanation purposes and do not contribute in sorting.

OUTPUT (with above example as values):

ALTERNATE CODE WHICH PRINT PASS/STEPS ALSO:

l1=list()

n=int(input("Enter the number of elements in list: "))

for e in range(n):

    ele=int(input("Enter value for element: "))

    l1.append(ele)

print("Original list :",l1)

for i in range (1,n):

    print(f"Pass {i}:")

#in the outer loop it will traverse through each index from 1 till the last

    for j in range(0,i):

# in 2nd loop each element will be compared with every element before it

        if l1[i]<l1[j]:

            l1[i],l1[j]=l1[j],l1[i]

            print(f"{l1} : Swapping {l1[i]} with {l1[j]}")

            continue

        print(f"{l1} : No swapping between {l1[i]} and {l1[j]}")

# if current element is smaller than any previous element

# then it would be shifted back

print("Final sorted list: ")

print(l1)