Software Development Python

How to perform Insertion Sort in Python?

How to perform Insertion Sort in Python?

Introduction

The Insertion sort algorithm is simpler and more efficient than the previous bubble sort algorithm. The concept of the insertion sort algorithm is based on the deck of cards, where we sort the playing cards according to a specific card. It has many advantages, but the data structure contains many efficient algorithms.

We compare our card hands with each other while playing cards. The majority of players prefer to sort the cards in ascending order so that they can quickly see which combinations they have at their disposal.

The Insertion Sort Concept

In the insertion sort, the array is split into two parts: an unsorted part and a sorted part.

The sorted section contains the array's first element, while the unsorted section contains the remainder of the array. The first element in the unsorted array is compared to the sorted array to determine which sub-array it belongs to.

It concentrates on inserting elements by moving all elements if the right-side value is less than the left-side value.

It will happen again and again until all of the elements are correctly inserted.

The insertion sort algorithm is shown below to sort the array using insertion sort.

  • I divided a list into two parts: sorted and unsorted.
  • Iterate through the array from arr[1] to arr[n].
  • Contrast the current element with the following element.
  • If the current element is smaller than the next element when compared to the element before it, Move one position up to make room for the swapped element.

# creating a function for insertion 
def insertion_sort(list1): 
 
        # Outer loop to traverse through 1 to len(list1) 
        for i in range(1, len(list1)): 
 
            value = list1[i] 
 
            # Move elements of list1[0..i-1], that are 
            # greater than value, to one position ahead 
            # of their current position 
            j = i - 1 
            while j >= 0 and value < list1[j]: 
                list1[j + 1] = list1[j] 
                j -= 1 
            list1[j + 1] = value 
        return list1 
            # Driver code to test above 
 
list1 = [10, 5, 13, 8, 2] 
print("The unsorted list is:", list1) 
 
print("The sorted list1 is:", insertion_sort(list1)) 

# Board Infinity

write your code here: Coding Playground

OUTPUT :

Explanation

  • In the preceding code, we defined a function called insertion sort (list1). Within the function -
  • We created a for loop to go through the list from 1 to len (list1).
  • In the for loop, assign a value from list1 to list1. The new value will be assigned to the value variable each time the loop iterates.
  • The elements of list1[0...i-1] that are greater than the value were then moved one position ahead of their current position.
  • We used a while to see if j is greater or equal to 0 and if the value is less than the first element of the list.
  • If both conditions are met, the first element is moved to the 0th index and the value of j is reduced, and so on.
  • Then we called the function, passed it to the list, and printed the result.

Insertion Sort Time & Space Complexity

  • Insertion sort is a slow algorithm that appears to be too slow for large datasets at times. It is, however, efficient for small lists or arrays.
  • The insertion sort has a time complexity of - O(n^2). Iteration is accomplished through the use of two loops.
  • Another significant advantage of the insertion sort is that it is used by the well-known sorting algorithm known as the Shell sort.
  • In insertion sort, the auxiliary space is O (1)

Conclusion

Although insertion sort is a simple and inefficient algorithm with many advantages, more efficient algorithms are available.

In this tutorial, we discussed the concept of the insertion sort and how it can be implemented in Python.