Insertion Sort in Python

Insertion Sort in Python

Sorting algorithms play a crucial role in computer science, and Insertion Sort is one of the most fundamental yet effective techniques, especially for small datasets. It is more efficient than Bubble Sort and operates similarly to sorting playing cards in hand.

In this blog post, we will explore Insertion Sort, understand its working mechanism, implement it in Python, and analyze its time complexity. Let’s get started!

Complete Python Course with Advance topics:-Click here

What is Insertion Sort?

Insertion Sort is an in-place, stable sorting algorithm that is simple yet useful for nearly sorted data or small-sized arrays. It builds a sorted list one element at a time by inserting each item into its correct position relative to the already sorted portion of the array.

Key Properties:

• In-place: Requires no extra space; sorting happens within the array itself.
• Stable: Maintains the relative order of equal elements.
• Efficient for small datasets: Works best when the number of elements is less than 10.
• Adaptive: Performs well when the array is nearly sorted.

Concept of Insertion Sort

Insertion Sort splits the array into two virtual parts:

1. Sorted Part – Initially contains the first element of the array.
2. Unsorted Part – Contains the rest of the array.

The algorithm picks an element from the unsorted part and inserts it into its correct position in the sorted part, shifting larger elements to the right.

Steps to Perform Insertion Sort:

1. Assume the first element is already sorted.
2. Pick the next element and compare it with elements in the sorted part.
3. Shift larger elements one position to the right to create space.
4. Insert the picked element into the correct position.
5. Repeat until all elements are sorted.

Let’s see an example.

Example Walkthrough

Given an unsorted array:

[10, 4, 25, 1, 5]

Sorting Process:

1. The first element 10 is considered sorted.
2. Pick 4. Since 4 < 10, shift 10 to the right and insert 4 before it: [4, 10, 25, 1, 5]
3. Pick 25. It is greater than 10, so it remains in place: [4, 10, 25, 1, 5]
4. Pick 1. Shift 25, 10, and 4 rightward and insert 1 at the beginning: [1, 4, 10, 25, 5]
5. Pick 5. Shift 25 and insert 5 before 10: [1, 4, 5, 10, 25]

Now, the array is sorted!

Python Implementation

Here’s how we can implement Insertion Sort in Python:

# Function for insertion sort
def insertion_sort(arr):
    for i in range(1, len(arr)):
        value = arr[i]
        j = i - 1
        while j >= 0 and value < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = value
    return arr

# Testing the function
arr = [10, 5, 13, 8, 2]
print("Unsorted List:", arr)
print("Sorted List:", insertion_sort(arr))

Output:

Unsorted List: [10, 5, 13, 8, 2]
Sorted List: [2, 5, 8, 10, 13]

Explanation:

1. The function loops through the array starting from index 1.
2. It picks an element and shifts the larger elements one position to the right.
3. It inserts the picked element in its correct place.
4. The loop continues until the entire array is sorted.

Sorting Custom Objects

Python allows sorting of objects using Insertion Sort by defining a custom comparison function. Below is an example of sorting points based on their x coordinate.

# Point Class
def insertion_sort(arr, compare_func):
    for i in range(1, len(arr)):
        value = arr[i]
        j = i - 1
        while j >= 0 and compare_func(arr[j], value):
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = value

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y
    def __str__(self):
        return f"({self.x}, {self.y})"

points = [Point(2,3), Point(4,4), Point(3,1), Point(8,0), Point(5,2)]

# Sorting by x-coordinate
insertion_sort(points, lambda a, b: a.x > b.x)
for point in points:
    print(point)

Output:

(2,3)
(3,1)
(4,4)
(5,2)
(8,0)

Time Complexity

Insertion Sort is not ideal for large datasets due to its O(n²) time complexity.

Despite this, it is efficient for small datasets and is used in Shell Sort as a subroutine.

Space Complexity:

• O(1) (Since it does not use additional storage apart from the input array)

Download New Real Time Projects :-Click here
Complete Advance AI topics:- CLICK HERE

Conclusion

Insertion Sort is a simple, stable, and in-place sorting algorithm. Although inefficient for large datasets, it is useful in scenarios where data is nearly sorted. We have covered its working principle, Python implementation, sorting custom objects, and time complexity analysis.

For more programming tutorials, visit UpdateGadh—your go-to platform for coding insights and solutions!

Insertion Sort in Python
selection sort in python
insertion sort algorithm
insertion sort in python with example
insertion sort in python using list
insertion sort in python using for loop
insertion sort in python user input
insertion sort in java
Insertion Sort in Python
insertion sort in python without using function
python compiler
insertion sort in python w3schools