Insertion Sort in Python

Introduction:

Insertion sort is a classic sorting algorithm that can be effectively implemented using Python. This tutorial provides a detailed guide to implementing the insertion sort algorithm. By following practical examples and explanations, you’ll grasp the inner workings of insertion sort and how it efficiently organizes elements in ascending order.

Code:

def insertion_Sort(list3):
    n = len(list3)
    for i in range(n):  # Traverse through all elements
        temp = list3[i]  # Store the current element in a temporary variable
        j = i - 1  # Initialize the index of the previous element

        # Move elements of list3[0..i-1], that are greater than temp,
        # to one position ahead of their current position
        while j >= 0 and temp < list3[j]:
            list3[j + 1] = list3[j]  # Shift the element to the right
            j = j - 1

        # The loop above will stop when we find the correct position for temp
        # (i.e., when temp is not smaller than the element to its left).
        # Now, place temp in its correct position
        list3[j + 1] = temp

# Example usage
numList = [8, 7, 13, 1, -9, 4]
insertion_Sort(numList)

print("The sorted list is:")
for i in range(len(numList)):
    print(numList[i], end=" ")

Logic:

1. Define the insertion_sort function that takes a list list3 as input.
2. Get the length of the list n.
3. Iterate through each element of the list using a loop:
4. Store the current element in the variable temp.
5. Initialize the index j to the previous element.
6. Move elements greater than temp one position ahead.
7. Place temp in its correct position in the sorted part of the list.
8. The sorted list is printed after the sorting process is complete.

Output:

>The sorted list is:

>>-9 1 4 7 8 13