Insertion Sort Algorithm in Python

1. Steps to Perform Insertion Sort in Python
2. Insertion Sort Algorithm in Python
3. Implementation of Insertion Sort in Python
4. Complexity of Insertion Sort Algorithm in Python
5. Features of Insertion Sort in Python
6. Binary Insertion Sort in Python

Insertion sort algorithm’s mechanism is like playing cards. Initially, we take the first card and assume it’s already sorted.

Thus, the remaining cards are the unsorted list. Then, we will pick cards from this unsorted list one by one and compare them with the cards in the sorted list.

This way, we can find a suitable position for the card and place it accordingly. Repetition of this process gives us the sorted pack of cards.

Insertion sort also works this way. As the name says, we make comparisons while insertion of elements.

Steps to Perform Insertion Sort in Python

Let us take an unsorted array with these elements:

15, 11, 17, 3, 5

We take the first element that is already sorted by convention.

` 15 `, 11, 17, 3, 5

We will loop through i = 1 to i= 4 from the second element to the last. When i =1, we compare 11 with its predecessors. Since 11 is smaller than 15, we move 15 and insert 11 before it.

` 11 `, ` 15 `, 17, 3, 5

For i = 2, we compare 17 with its predecessors. This time, since 17 is greater than both 11 and 15, it goes after 15.

` 11 `, ` 15 `, ` 17 `, 3, 5

For i = 3, we compare 3 with its predecessors. 3 will move to the beginning now.

` 3 `, ` 11 `, ` 15 `, ` 17 `, 5

For i = 4, we compare 5 with its predecessors. 5 will be placed after 3 and before 11.

` 3 `, ` 5 `, ` 11 `, ` 15 `, ` 17 `

This is how we get the sorted array using insertion sort in python.

Insertion Sort Algorithm in Python

By convention, we assume the first element to be already sorted in the list. The rest of the list is considered to be unsorted.

After that, we will start inserting the elements from the unsorted part to the sorted part by maintaining the order in the sorted part of the list. We will use the following steps.

• Select the next element from the unsorted list and mark it as the key.
• Pick the key and compare it with all the elements present in the sorted list.
• If the key element is greater than the element in the sorted array, move to the next element in the list. Else, move the smaller elements of the list to the left.
• Insert the key in the sorted list at the correct position to maintain order in the sorted list.
• Repeat the above steps until the entire list gets sorted.

Implementation of Insertion Sort in Python

Here is the code to implement Insertion sort in the Python language.

# Code in Python

# Function that performs Insertion sort
def Insertion_sort(arr):

    # Loop till the last element starting from the second one
    for i in range(1, len(arr)):

        key_ele = arr[i]

        # set the position of elements based on their value
        t = i - 1
        while t >= 0 and key_ele < arr[t]:
            arr[t + 1] = arr[t]
            t -= 1
        arr[t + 1] = key_ele


arr = [23, 45, 22, 6, 11]
Insertion_sort(arr)
for i in range(len(arr)):
    print("% d" % arr[i])

Output:

6
11
22
23
45

We first define a function Insertion_sort(). We apply the sorting logic inside this function.

We iterate through the array from the second item and compare the key with already sorted elements. At each iteration, we store the element’s value from the list in another variable, key_ele.

Then, we use a variable to store the value of the index of the last element. This way, we can use the value of t and key_ele to make comparisons.

Based on the value of the key element, we move the elements and place the key in the sorted list.

In the function definition, we declare an array. In Python, we call it a list.

Then, we call the insertion_sort function. We pass the list as an argument in this function.

The function returns the list after sorting it. At last, we can use the for loop to print the sorted list.

Complexity of Insertion Sort Algorithm in Python

Time Complexity

Complexity in the Best Case - The array is already sorted. Thus, no sorting is required, and the complexity in the best case is O(n).

Complexity in the Average Case - The array is neither ascending nor descending order. It is jumbled randomly. The average time complexity is O(n^2).

Complexity in the Worst Case - Arranging an array in increasing order when it is already sorted in decreasing order, reversing an array. The worst-case time complexity is O(n^2).

Space Complexity

Insertion sort’s space complexity is O(1) since we need an extra variable for performing swap operations.

The insertion sort algorithm is based on the incremental paradigm, and it is a stable algorithm.

Features of Insertion Sort in Python

• This algorithm is simple to implement.
• Insertion sort is efficient for working with a small set of elements.
• We can even use it on data that is already sorted. It is an adaptive algorithm.

Binary Insertion Sort in Python

Binary insertion sort is the improvised version of insertion sort, which helps in reducing the number of comparisons that take place in the normal insertion sort.

The idea is simple - we use binary search to find the correct position of the key. This way, we can reduce the complexity of searching to O(log i) from O(i) for the i-th iteration.

However, the worst-case complexity remains O(n^2).

To sum it up, we learned about Insertion sort and its implementation in Python.

Insertion sort is efficient for sorting a small number of elements, but we should use other algorithms like merge sort and quick sort for large sets. The simplicity of this algorithm is what makes it stand out.