In this article, we will talk about the insertion sort algorithm in Python. This is the simplest sorting algorithm and is more efficient or powerful for handling the data with a small range or sorting a partially sorted list. A procedure called the insertion sort is used to rank the numbers in arrays either ascending or descending way. This algorithm uses an in-place and stable approach to sort the array efficiently. Here, we will explain in detail about this sort algorithm and implement the insertion sort algorithm in Python with the help of examples. Let’s elaborate on how the insertion sort works.

How Does the Insertion Sort Work?

The working of insertion sort is discussed in detail here. The numbers are sorted using the insertion sort. It repeatedly places the subsequent unsorted element in the appropriate spot in the previously sorted list. The fundamental concept is to compare the second member to the array’s first element which is presumably already sorted. If the second element is a smaller value than the first, it is switched. This procedure is repeated for the remaining array elements. The worst and average cases of insertion sort have an O(n2) time complexity, whereas the best case has an O(n) time complexity.

Example 1:
We take a linear example to understand the concept of insertion sort. The reference code is provided in the following:

As seen in this example, we defin an insertion sort function at line 1. This implementation takes a list of numbers as input and sorts the list in ascending order. We assign the “arr” variable as a list in this example. After that, we start the outer loop which checks the index of the array. The “for” loop is used here. The range begins at 1, which is the second number in an array, and continues through the loop to the last element.

Inside this loop, we initialize a key variable that checks the index value one by one. Following that, we create a variable that holds the array's value (n-1). The inner loop now starts to check the array values. The inner loop starts at the current index of the outer loop and compares the current element with the previous element. If the previous element is larger, it is shifted to the right and the current element's index is decreased. This continues until the correct position for the current element is found.

The current element is placed into the appropriate spot after the inner loop is finished. In the end, we declare and initialize the array named “arr”. We used this array in the previously-described insertion function to perform the sorting on the array. Lastly, we provide the array in the print statement to display the outcome on the console.

The output of this example program is given in the following:

Example 2:
We will also explain the insertion sorting in Python with the help of another example. We create and run this example using any Python tool such as PyCharm or Jupiter Notebook. The reference code for this other example is attached in the following:

We declare an array for sorting purposes by defining the function named “sortArray”. We use a loop to traverse the array and start the searching by index “1”. We put the length of the array and index “1” in the range function where the loop is executed. We put another variable in which we currently store the value of the loop iteration “i” in the array and assign the value to “temp” variable. We store the previous value which is probably the first element of the array from which we compare the “temp” variable to search if this value is greater or smaller than the value that is stored in the “temp” variable and name that variable as “previousElement”.

The inner loop takes the value that is present in the “previousElement” variable to check if the value is greater than “0”. Then, we compare the two variables named “temp” and “previousElement” that are stored in the array. This value is passed until the loop remains not end. If the value of the array that is stored in “previousElement” is “+1”, it means that the loop changing value is lesser than the previous value of the array that is stored in index “0”. Then, we swap these two variables through which the lesser value is shifted towards index “0” and the greater value is moved in place of another variable.

Here, we write the logic to swap the elements in the array to sort the elements. Now, all values of the array are checked one by one. Changing the position of values are lesser and shifted towards the start of the array. Let’s take this array for consideration. We start the array with index “1”. This means that we first take “66”. Then, we compare the value of “66” to the previous value that is stored in index “0” which is “45”. Now, “45” is lesser than “66”. So, we then swap the variable that stores the value of “66”. Then, we assign the previous value of the array in the “temp” variable. Now, we store the value of “45” in the “temp” variable.

Lastly, we assign the value that is stored in “array [previousElement +1]” where the next value to the previous value is stored. After that, we store the next previous value in temp to start sorting again. In this way, we swap the larger and smaller values. So, until the loop is valid, the elements of the array are stored quickly, one by one. At the end of the code, we display the result of this array on the console through the print statement.

Here, the output of this array is displayed on the console since the result of the stored array is

Conclusion

We conclude that insertion sorting is the most important type of sorting that is used to sort all the elements of an array in Python. Insertion sort is a stable and in-place but inefficient algorithm that has many benefits which we discussed with the help of examples. Here, we split the array into two parts: sorted and unsorted. The comparison between these two parts created the sorted array at the end.