Insertion Sort Algorithm in Python

Insertion Sort in Python

The Insertion Sort is a simple yet more effective algorithm compared to the earlier Bubble Sort algorithm. The principle behind the Insertion Sort algorithm is similar to sorting a deck of cards, where cards are organized based on a specific card. While it offers several benefits, there are also numerous more efficient algorithms present within data structures.

During card games, players evaluate their hands against one another. The majority of participants prefer to arrange their cards in ascending order, allowing for a swift assessment of the combinations available to them.

The implementation of insertion sort is straightforward and uncomplicated, as it is typically introduced in introductory programming courses. This algorithm operates in-place and maintains stability, making it particularly advantageous for arrays that are nearly sorted or contain a small number of elements.

The insertion sort algorithm is relatively slow due to its reliance on nested loops to sort the elements.

Let's understand the following terms.

What is the meaning of in-place and stable?

✅ In-place: The in-place algorithm requires additional space without caring for the input size of the collection. After performing the sorting, it rewrites the original memory locations of the elements in the collection.
✅ Stable: The stable is a term that manages the relative order of equal objects from the initial array.

A key advantage of insertion sort is that it does not necessitate prior knowledge of the array size and processes one element at a time.

The advantageous aspect of insertion sort is that as we add more elements to be sorted, the algorithm positions them correctly without the need to execute a full sort.

For arrays with a size of fewer than 10 elements, insertion sort is generally more effective. Next, we will explore the principles of insertion sort.

Concept of Insertion Sort

In the insertion sort algorithm, the array is conceptually divided into two sections: one that is unsorted and another that is sorted.

The sorted section includes the initial element of the array, while the remaining unsorted segment contains the rest of the elements. The first element from the unsorted array is evaluated against the sorted section to determine its appropriate placement within a suitable sub-array.

It emphasizes the process of inserting elements by shifting all items when the value on the right is less than that on the left.

This process will continue until every element is positioned in its appropriate location.

To sort the array using insertion sort below is the algorithm of insertion sort.

✅ Spilt a list in two parts - sorted and unsorted.
✅ Iterate from arr[1] to arr[n] over the given array.
✅ Compare the current element to the next element.
✅ If the current element is smaller than the next element, compare to the element before, Move to the greater elements one position up to make space for the swapped element.

Insertion Sort Example

Let's understand the following example.

We will examine the initial element in the sorted array in the subsequent array.

[10, 4, 25, 1, 5]

The first step to add 10 to the sorted subarray

[ 10 , 4, 25, 1, 5]

We begin by selecting the initial element from the unsorted array, which is 4. This value is then assigned to a new variable named temp. Next, we observe that 10 is greater than 4, prompting us to shift 10 to the right, thereby replacing the 4 that was originally stored.

[ 10 , 10, 25, 1, 5] (temp = 4)

In this case, since 4 is smaller than every element in the sorted subarray, we place it at the initial index position.

[ 4, 10, 25, 1, 5]

We have two elements in the sorted subarray.

Next, examine the value 25, which we have stored in the temp variable. It is true that 25 is greater than 10 and also greater than 4. Consequently, we place it in the third position and incorporate it into the sorted sub-array.

[ 4, 10, 25, 1, 5]

We examine the number 1 once more and store it in a temporary variable. Since 1 is smaller than 25, it replaces the value of 25.

[ 4, 10, 25, 25, 5] 10>1 then it overwrites again

[ 4, 25, 10, 25, 5]

[ 25, 4, 10, 25, 5] 4>1 now assign the value of temp = 1

[ 1, 4, 10, 25 , 5]

At this point, there are 4 components in the sorted subarray. Since 5 is less than 25, we will move 25 to the right and place temp = 5 on the left.

[ 1, 4, 10, 25 , 25] put temp = 5

At this point, we obtain the sorted array by directly inserting the temporary value.

[1, 4, 5, 10, 25]

The given array is sorted.

Implementation of Insertion Sort

The execution of insertion is relatively straightforward. We will be utilizing an array of integers in Python for this implementation. Let's examine the following example -

Example


# 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))

Output:

Output


The unsorted list is: [10, 5, 13, 8, 2]

The sorted list1 is: [2, 5, 8, 10, 13]

Explanation:

In the above code, we have created a function called insertion_sort(list1). Inside the function -

✅ We defined for loop for traverse the list from 1 to len(list1).
✅ In for loop, assigned a values of list1 in value Every time the loop will iterate the new value will assign to the value variable.
✅ Next, we moved the elements of list1[0…i-1], that are greater than the value, to one position ahead of their current position.
✅ Now, we used the while to check whether the j is greater or equal than 0, and the value is smaller than the first element of the list.
✅ If both conditions are true then move the first element to the 0 th index and reduce the value of j and so on.
✅ After that, we called the function and passed the list and printed the result.

Sorting Custom Objects

Python offers the capability to modify the algorithm through a user-defined object. We will develop a custom class and alter the primary comparison attribute while aiming to maintain the same code structure as previously mentioned.

To sort the objects differently, it is necessary to overload the operators. However, we can also provide an additional argument to the insertion_sort function by utilizing a lambda function. The lambda function serves as a practical tool when invoking the sorting method.

Let us examine the subsequent illustration of organizing custom objects.

First, we are defining the Point class:

Python Program

Example


# Creating Point class

class Point:

    def __init__(self, a, b):

        self.a = a

        self.b = b

    def __str__(self):

        return str.format("({},{})", self.a, self.b)

def insertion_sort(list1, compare_function):

    for i in range(1, len(list1)):

        Value = list1[i]

        Position = i

        while Position > 0 and compare_function(list1[Position - 1], Value):

            list1[Position] = list1[Position - 1]

            Position = Position - 1

        list1[Position] = Value

U = Point(2,3)

V = Point(4,4)

X = Point(3,1)

Y = Point(8,0)

Z = Point(5,2)

list1 = [U,V,X,Y,Z]

# We sort by the x coordinate, ascending

insertion_sort(list1, lambda x, y: x.a > y.a)

for point in list1:

    print(point)

Output:

Output


The points are in the sorted order

(2,3)

(3,1)

(4,4)

(5,2)

(8,0)

By utilizing the aforementioned code, we are able to arrange the coordinate points. This approach is effective for any variety of lists.

Time Complexity in Insertion Sort

Insertion sort is considered a relatively slow algorithm; at times, it appears excessively slow for large datasets. Nevertheless, it proves to be effective for smaller arrays or lists.

The time complexity associated with insertion sort is O(n²). It employs two loops for the purpose of iteration.

An additional significant benefit of insertion sort is its application in the well-known sorting algorithm known as Shell sort.

The auxiliary space in insertion sort: O(1)

Conclusion

Insertion sort is a straightforward yet inefficient sorting algorithm that offers several benefits; however, there are more efficient algorithms that can be utilized.

This tutorial has covered the idea of insertion sort and its execution through the Python programming language.