Program for Insertion Sort in Python

Python Program for Insertion Sort

Python / By

What exactly is sorting? What’s the big deal about it? In this part, we will attempt to answer these questions.

We’ve sorted everything from books in a library to words in a dictionary to database entries and processor instructions on a number of occasions.
This means that when we sort things, we must first determine the criteria by which we will organize the items in the sequence provided to us. For the purposes of this lesson, we’ll suppose that the criteria is a number’s value, and we’ll sort a set of numbers.

The most significant goal of sorting in computer science is to create efficient algorithms. Binary Search is a lightning-fast search algorithm that would be impossible to use in an unsorted set of objects.

On sorted data, almost all set operations are extremely fast.

Apart from creating efficient algorithms, sorting is employed when a program’s sole purpose is to sort things, such as when working with a deck of cards. As a result, sorting algorithms are one of the most important things for a programmer to understand.

Sorting algorithms are programs that reorganize a huge number of elements into a certain order, such as from highest to lowest, or vice versa, or even alphabetically.

These algorithms take an input list, process it (that is, perform operations on it), and then return a sorted list.
The importance of sorting comes from the idea that if data is kept in a sorted fashion, data searching may be greatly improved. Sorting can also be used to display data in a more legible fashion. The instances of sorting in real-life circumstances are as follows:

Telephone Directory :The telephone directory keeps track of people’s phone numbers, which are classified by their names so that they may be quickly found.

Dictionary : The dictionary organizes terms alphabetically so that searching for a specific word is simple.

Examples:

Sorting in Ascending order

Example1:

Input:

givenlist = [8, 132, 22, 34, 57, 2, 1, 9, 45, 87, 63, 80, 26, 65, 132]

Output:

printing the list before sorting :
8 132 22 34 57 2 1 9 45 87 63 80 26 65 132 
printing the list after sorting :
1 2 8 9 22 26 34 45 57 63 65 80 87 132 132

Example2:

Input:

givenlist = ["hello", "this", "is", "BTechGeeeks", "python", "new", "online",
                   "platform", "for", "all", "students", "who", "are", "excited", "about", "coding"]

Output:

printing the list before sorting :
hello this is BTechGeeeks python new online platform for all students who are excited about coding 
printing the list after sorting :
BTechGeeeks about all are coding excited for hello is new online platform python students this who

Sorting in descending order example

Example 3:

Input:

Input:

givenlist = [8, 132, 22, 34, 57, 2, 1, 9, 45, 87, 63, 80, 26, 65, 132]

Output:

printing the list before sorting :
8 132 22 34 57 2 1 9 45 87 63 80 26 65 132 
printing the list after sorting :
132 132 87 80 65 63 57 45 34 26 22 9 8 2 1

Example4:

Input:

givenlist = ["hello", "this", "is", "BTechGeeeks", "python", "new", "online",
                   "platform", "for", "all", "students", "who", "are", "excited", "about", "coding"]

Output:

printing the list before sorting :
hello this is BTechGeeeks python new online platform for all students who are excited about coding 
printing the list after sorting :
who this students python platform online new is hello for excited coding are all about BTechGeeeks

Program for Insertion Sort in Python

Explore more instances related to python concepts from Python Programming Examples Guide and get promoted from beginner to professional programmer level in Python Programming Language.

1)Insertion Sort Introduction

While playing cards, we compare the hands of cards to one another. The majority of players choose to sort the cards in ascending order so that they can immediately see which combinations they have.

Because it’s usually taught in the first programming class, the insertion sort implementation is simple and straightforward. It’s a stable and in-place algorithm that works well with nearly-sorted or fewer elements.

Because it uses a nested loop to sort the elements, the insertion sort method is slow.

The insertion sort, on the other hand, does not require prior knowledge of the array size and only gets one member at a time.

The advantage of the insertion sort is that if we input more elements to be sorted, the algorithm puts them in their right order without having to do a full sort.

It is more efficient for tiny arrays (less than 10). Let’s look at the insertion sort concepts now.

2)Algorithm and Working of insertion Sort

In the sorted section, there is only one element at first, which is the very first one (The sorted section is at the beginning of the list).

We need an index to keep track of where the unsorted portion begins, and since the unsorted portion begins with the second element, the index must be 1. (In the case of Python).
Now we try to locate the first element from the unsorted portion (the element at the unsorted index) in the sorted part.

We do this by comparing it to each element in the sorted section one by one until we locate an element that is smaller (in ascending order) or larger (in descending order) than the new element.

Then we place it in the appropriate location and reorder all of the sorted elements to make room for the new element. The procedure is repeated until the array is completely sorted.

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

The first element of the array is in the sorted subpart, while the rest of the array is in the unsorted subpart. The initial element in the unsorted array is compared to the sorted array to determine which sub-array it belongs to.

If the right-side value is smaller than the left-side value, it focuses on inserting the elements by relocating all elements.

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

The algorithm for sorting an array using insertion sort is shown below.

  • divide a list into two parts: sorted and unsorted.
  • Iterate through the array from arr[1] to arr[n].
  • Compare the current element with the following element.
  • If the current element is less than the next element as compared to the previous element, To make space for the swapped element, move one position up to the bigger elements.

3)Implementation:

Below is the implementation of Insertion Sort:

Sorting the given list in Ascending Order:

# function which implements the insertion_sort  algorithm for givenlist
def insertion_sort(givenlist):

    # Traverse the list from 1 to length of the list
    for i in range(1, len(givenlist)):

        elementValue = givenlist[i]

        # List1[0..i-1] elements that are greater than value
        # should be moved one position ahead of their current location.
        j = i - 1
        while j >= 0 and elementValue < givenlist[j]:
            givenlist[j + 1] = givenlist[j]
            j -= 1
        givenlist[j + 1] = elementValue


# given list
givenlist = ["hello", "this", "is", "BTechGeeeks", "python", "new", "online",
             "platform", "for", "all", "students", "who", "are", "excited", "about", "coding"]
# printing the list before sorting
print("printing the list before sorting :")
for i in givenlist:
    print(i, end=" ")
print()
# passing this given list to insertion_sort function which sorts the given list
insertion_sort(givenlist)
# printing the list after sorting
print("printing the list after sorting :")
for i in givenlist:
    print(i, end=" ")

Output:

printing the list before sorting :
hello this is BTechGeeeks python new online platform for all students who are excited about coding 
printing the list after sorting :
BTechGeeeks about all are coding excited for hello is new online platform python students this who

Explanation : Here we can see that the given list of strings is sorted in Ascending order

Sorting the given list in Descending order

Below is the implementation of InsertionSort:

# function which implements the insertion_sort  algorithm for givenlist
def insertion_sort(givenlist):

    # Traverse the list from 1 to length of the list
    for i in range(1, len(givenlist)):

        elementValue = givenlist[i]

        # List1[0..i-1] elements that are less than value
        # should be moved one position ahead of their current location.
        j = i - 1
        while j >= 0 and elementValue > givenlist[j]:
            givenlist[j + 1] = givenlist[j]
            j -= 1
        givenlist[j + 1] = elementValue


# given list
givenlist = ["hello", "this", "is", "BTechGeeeks", "python", "new", "online",
             "platform", "for", "all", "students", "who", "are", "excited", "about", "coding"]
# printing the list before sorting
print("printing the list before sorting :")
for i in givenlist:
    print(i, end=" ")
print()
# passing this given list to insertion_sort function which sorts the given list
insertion_sort(givenlist)
# printing the list after sorting
print("printing the list after sorting :")
for i in givenlist:
    print(i, end=" ")

Output:

printing the list before sorting :
hello this is BTechGeeeks python new online platform for all students who are excited about coding 
printing the list after sorting :
who this students python platform online new is hello for excited coding are all about BTechGeeeks

Explanation : Here we can see that the given list of strings is sorted in Descending order

4)Time Complexity

An array would be sorted in reverse order in the worst-case situation. In the Insertion Sort function, the outer for loop iterates n-1 times.
The inner for loop would swap once, then two, and so on in the worst-case situation. The number of swaps is then 1 + 2 +… + (n – 3) + (n – 2) + (n – 1), giving Insertion Sort an O(n2) time complexity.

5)Conclusion

We examined how Insertion Sort is comparable to how we sort things in real life, examined the technique it employs, and implemented Insertion Sort in Python in this tutorial.

After that, we spoke about how the algorithm works and ran it on an unsorted sample to see how it works. Finally, we used the actual output of the code to verify the dry run. Insertion sort, like Bubble Sort, has an O (n^2)level of complexity .

Similarly, doubling the input size increases the time it takes to execute by four times, and tripling the input size increases the time it takes to execute by nine times.

The algorithm is inefficient for practical application as a result of this, but it is a highly intuitive approach.
Related Programs: