Insertion Sort in Ascending Order in Python

1. Introduction

In this blog post, we will learn how to write a Python program to sort an array of integers in an Ascending Order using the Insertion Sort algorithm.

Insertion sort is a simple and intuitive sorting algorithm. It works by building a sorted segment of the array one item at a time. The algorithm iterates over the list, and during each iteration, it expands the sorted segment by inserting the current element into its correct position.

2. Program Overview

1. insertion_sort(): This is the main function that implements the Insertion Sort algorithm.

2. A sample list is provided to showcase how the algorithm works.

3. Code Program

def insertion_sort(arr):
    # Traverse through 1 to len(arr)
    for i in range(1, len(arr)):
        key = arr[i]  # The current element to be compared and placed in the sorted section of the array
        j = i - 1
        
        # Move elements of arr[0..i-1] that are greater than key
        # to one position ahead of their current position
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

def print_list(arr):
    for i in arr:
        print(i, end=" ")
    print()

# Driver code to test the function
if __name__ == "__main__":
    arr = [12, 11, 13, 5, 6]
    print("Unsorted list is:")
    print_list(arr)

    insertion_sort(arr)
    print("\nSorted list is:")
    print_list(arr)

Output:

Unsorted list is:
12 11 13 5 6 

Sorted list is:
5 6 11 12 13 

4. Step By Step Explanation

1. insertion_sort(): This function starts with the second element (index 1) as the first one is considered sorted by default. For each subsequent element, the function goes back and compares it with elements in the sorted segment. If the current element is smaller than the comparison element, the latter is moved one position up to make space for the current element. The procedure is repeated until the current element is larger or the start of the array is reached.

2. print_list(): A utility function to print the elements of the array.

3. Driver code: Demonstrates the Insertion Sort algorithm using a sample list.

Insertion Sort is efficient for small lists or partially sorted lists. However, its time complexity in the worst case is O(n^2), making it less efficient for large datasets compared to more advanced algorithms like Merge Sort or Quick Sort.

Related Python Programs on Sorting Algorithms

1. Bubble Sort in Ascending Order in Python
2. Bubble Sort in Descending Order in Python
3. Selection Sort in Ascending Order in Python
4. Selection Sort in Descending Order in Python
5. Insertion Sort in Descending Order in Python
6. Insertion Sort in Ascending Order in Python
7. Merge Sort in Ascending Order in Python
8. Merge Sort in Descending Order in Python
9. Quick Sort in Ascending Order in Python
10. Quick Sort in Descending Order in Python
11. Heap Sort in Ascending Order in Python
12. Heap Sort in Descending Order in Python