Insertion Sort Algorithm in Python.

Insertion Sort is a simple sorting algorithm that is used to sort the array/list elements in ascending or descending order. In this article, we will discuss the algorithm in detail with an example and Python code implementation.

Insertion Sort Algorithm.

Insertion Sort is a simple sorting algorithm that builds the final sorted array gradually by iterating through the elements. It divides the array into two parts: the sorted part and the unsorted part. It repeatedly takes an element from the unsorted part and places it in its correct position within the sorted part by shifting larger elements to the right. This process continues until all elements are in their correct positions, resulting in a fully sorted array. 

The insertion sort algorithm starts with the assumption that the first element is already sorted and then compares subsequent elements, inserting them into the correct position in the sorted part while shifting larger elements as needed. 

Algorithm steps:

• Step 1: Assume the first element is already sorted and consider the second element.

• Step 2: For each element in the unsorted part, compare it with elements in the sorted part.

• Step 3: If the element is smaller, shift larger elements in the sorted part to the right and insert the element at the correct position.

• Step 4: Continue the process until all elements are sorted.

Example:

Let's consider an array [5, 2, 4, 6, 1, 3] and apply Insertion Sort step by step:

1. Below is the condition of the Initial Array.

2. Iteration 1: The first element (5) is already sorted. Consider the second element (2) and compare it with the first. Since 2 < 5, swap them.

3. Iteration 2: Consider the third element (4). Compare it with elements in the sorted part (2, 5). Shift larger elements (5) to the right and insert 4 at the correct position.

4. Iteration 3: Consider the fourth element (6). It is larger than the sorted elements, so leave it as it is.

5. Iteration 4: Consider the fifth element (1). Compare it with elements in the sorted part. Shift larger elements (2, 4, 5, 6) to the right and insert 1 at the correct position.

6. Iteration 5: Consider the sixth element (3). Compare it with elements in the sorted part. Shift larger elements (4, 5, 6) to the right and insert 3 at the correct position.

7. Our Final Sorted Array is [1, 2, 3, 4, 5, 6].

Python Program for Insertion Sort Algorithm.

# Python code Implementation of Insertion Sort
def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1

        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        
        arr[j + 1] = key

# Example
arr = [12, 11, 13, 5, 6]
insertion_sort(arr)
print("Sorted array:", arr)

Sorted array: [5, 6, 11, 12, 13]