Python Program For Insertion Sort (Simply Explained With Code)

In this guide, you will learn about the Python program for insertion sort.

We will explore the Python program for insertion sort, a popular sorting algorithm used to arrange elements in a specific order.

We will delve into the details of insertion sort and provide a step-by-step guide to implementing it in Python.

Whether you are a beginner or an experienced programmer, this article will equip you with the knowledge to effectively use insertion sort in your projects.

So let’s dive in!

Insertion sort is a simple and efficient sorting algorithm that builds the final sorted array one item at a time.

It is based on the principle of inserting an element into the correct position within a sorted subarray.

The algorithm iterates through the unsorted portion of the array, comparing each element to the elements in the sorted portion and shifting them if necessary.

This process continues until all elements are sorted.

Now, let’s take a look at the Python program for insertion sort.

We will walk through the code and explain each step to ensure a clear understanding of the implementation.

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key


array = [5, 2, 8, 12, 1]
print("Original Array:", array)
insertion_sort(array)
print("Sorted Array:", array)

You can run this code on our free Online Python Compiler.

Output

The insertion_sort() function takes an array arr as input and performs the insertion sort algorithm on it.

Let’s break down the steps involved:

Working: Python Program for Insertion Sort

1. The function starts by iterating through the array from the second element i = 1 to the last element len(arr). This is because the first element is considered already sorted.
2. Inside the loop, we store the current element arr[i] in the variable key. This element will be inserted into its correct position in the sorted subarray.
3. We initialize the variable j to i - 1, which points to the last element of the sorted subarray.
4. The while loop compares the element at index j with the key value. If the element is greater than the key, it is shifted one position to the right arr[j + 1] = arr[j]. This process continues until we find the correct position for the key or reach the beginning of the array j >= 0.
5. Once the correct position is found, we insert the key into the array at index j + 1 (arr[j + 1] = key).
6. The outer loop continues until all elements in the array are processed, resulting in a fully sorted array.

Let’s move on to further explore the intricacies of insertion sort.

Time Complexity: Python Program for Insertion Sort

Understanding the time complexity of an algorithm is crucial for evaluating its efficiency.

The time complexity of insertion sort can be analyzed based on the number of comparisons and shifts it performs.

The worst-case time complexity of insertion sort is O(n²), where n is the number of elements in the array.

This occurs when the input array is sorted in reverse order, requiring maximum comparisons and shifts for each element.

The best-case time complexity is O(n), which happens when the input array is already sorted.

On average, insertion sort has a time complexity of O(n²), making it less efficient than more advanced sorting algorithms like merge sort or quicksort.

However, insertion sort performs exceptionally well on small arrays or partially sorted arrays, as it has a relatively low overhead.

Insertion sort, despite its simplicity, possesses several advantages and disadvantages. Let’s examine them in detail.

Advantages: Python Program for Insertion Sort

1. Simplicity: The algorithm is straightforward to understand and implement, making it an excellent choice for beginners and quick prototypes.
2. Efficiency for Small Arrays: Insertion sort performs well on small arrays or partially sorted arrays, as it has a lower overhead compared to more complex algorithms.
3. In-Place Sorting: The algorithm sorts the array in-place, meaning it does not require additional memory beyond the original array.

Disadvantages: Python Program for Insertion Sort

1. Quadratic Time Complexity: The worst-case and average time complexity of insertion sort are both O(n²), making it inefficient for large arrays.
2. Limited Scalability: Due to its quadratic time complexity, insertion sort is not suitable for sorting large datasets or real-time applications that demand high performance.
3. Lack of Adaptive Behavior: Insertion sort performs the same number of comparisons and shifts regardless of the input order, which can lead to inefficiency when dealing with partially sorted arrays.

Despite its limitations, insertion sort remains a valuable sorting algorithm in specific scenarios. Its simplicity and efficiency on small datasets make it a viable choice for certain applications.

To provide a clearer understanding of how insertion sort works, let’s walk through an example. We will use the following array as input: [5, 2, 8, 12, 1].

Explanation: Python Program for Insertion Sort

1. Iteration 1: The first element, 5, is already considered sorted. The second element, 2, is smaller than 5, so it needs to be shifted. After the first iteration, the array becomes [2, 5, 8, 12, 1].
2. Iteration 2: The third element, 8, is greater than 5 and is in the correct position. The array remains unchanged at this point.
3. Iteration 3: The fourth element, 12, is greater than 8 and is in the correct position. The array remains unchanged.
4. Iteration 4: The fifth element, 1, is smaller than 12, 8, 5, and 2. It needs to be shifted until it finds its correct position. After the last iteration, the array becomes [1, 2, 5, 8, 12].

By the end of the iterations, the array is fully sorted in ascending order.

This step-by-step walkthrough demonstrates how insertion sort gradually builds the sorted subarray, shifting elements as necessary.

Q: What is the purpose of insertion sort?

Insertion sort is used to arrange elements in a specific order, typically in ascending or descending order.

It is commonly employed when dealing with small arrays or partially sorted arrays.

Q: Is insertion sort faster than other sorting algorithms?

Insertion sort has a time complexity of O(n²), making it less efficient than some other sorting algorithms, such as merge sort or quicksort.

However, it performs well on small arrays or partially sorted arrays due to its low overhead.

Q: Can insertion sort handle large datasets?

Insertion sort is not suitable for sorting large datasets due to its quadratic time complexity.

Other sorting algorithms, like merge sort or quicksort, are more efficient in handling large datasets.

Q: Can insertion sort handle different data types?

Yes, insertion sort can be used to sort arrays containing different data types, such as integers, floating-point numbers, or strings.

The comparison operation used in the algorithm can be customized based on the data type being sorted.

Q5: Are there any optimized versions of insertion sort available?

Yes, there are optimized versions of insertion sort, such as binary insertion sort, which reduces the number of comparisons by utilizing binary search to find the correct position for each element.

These optimized versions can improve the efficiency of the algorithm in certain cases.

Q6: How does insertion sort compare to bubble sort?

Insertion sort and bubble sort are both simple sorting algorithms with quadratic time complexity.

However, insertion sort performs better than bubble sort on average, as it performs fewer comparisons and shifts.

In conclusion, the Python program for insertion sort provides an effective way to sort elements in a specific order.

Despite its quadratic time complexity, insertion sort is valuable in certain scenarios, such as sorting small arrays or partially sorted arrays.

By understanding the steps involved and the advantages and disadvantages of insertion sort, you can make informed decisions when choosing a sorting algorithm for your projects.

Remember to consider the nature and size of your dataset to select the most appropriate sorting algorithm.

While insertion sort may not be the most efficient for large datasets, it remains a valuable tool in your programming arsenal.

Learn more about Python data structures and algorithms.