What is insertion sort with example?

While learning Data Structure and Algorithm (DSA) you must have come across different sorting techniques like merge sort, selection sort, bubble sort, insertion sort, etc. In today’s article, we will be discussing in detail insertion sort with an example.

Introduction

Insertion sort is a simple sorting technique that works by traversing through a sequence/list of items, comparing each immediate next element, and inserting it into the correct position in the list

For example, let’s assume a list of numbers that we want to sort in small to big order [8, 5, 6, 9, 3], we would compare the first element, 8, to the second element, 5. Since 5 is smaller than 8, we swap them, resulting in the list [5, 8, 6, 9, 3]. We would then compare the second element, 8, to the third element, 6, and since 6 is smaller than 8, we swap them, resulting in the list [5, 6, 8, 9, 3]. This process continues until the list is fully sorted, with the final sorted list being [3, 5, 6, 8, 9].

This sorting algorithm is very easy to understand and implement, and it is logical for small lists. However, it becomes less efficient as the list size increases and is unsuitable for large lists. Insertion sort is also a stable algorithm, meaning if there is any element in the list with the same value it will retain its order of position after the sort is complete. we can use this sorting technique with partially sorted lists and is useful in a variety of applications such as sorting data in databases and sorting items in inventory systems. It is important to consider the limitations of insertion sort and choose the appropriate algorithm for the task at hand.

History of insertion sort

Origins and development of the algorithm: Insertion sort has a long history, with early versions dating back to the 18th century. It was first described in detail by James V. Wheatley in 1953 and has since become a popular choice for sorting small lists.

How insertion sort works

A step-by-step explanation of the sorting process is as follows:

Insertion sort works by iterating through a list of items, comparing each element to the ones that come before it, and inserting it into the correct position in the list. This process is repeated until the list is fully sorted. To illustrate this process, let’s use the example of a list of numbers that we want to sort in ascending order: [22, 6, 15, 48, 1].

• Compare the first element, 22, to the second element, 6. Since 15 is smaller than 22, we swap them, resulting in the list [6, 22, 15, 48, 1].
• Compare the second element, 22, to the third element, 15. Since 15 is smaller than 22, we swap them, resulting in the list [6, 15, 22, 48, 1].
• Compare the third element, 22, to the fourth element, 48. Since 48 is larger than 22, no swap is necessary.
• Compare the fourth element, 48, to the fifth element, 1. Since 1 is smaller than 48, we swap them, resulting in the list [6, 15, 22, 1, 48].
• Compare the third element, 22, to the fourth element, 1. Since 1 is smaller than 22, we swap them, resulting in the list [6, 15, 1, 22, 9].
• Compare the second element, 15, to the third element, 1. Since 1 is smaller than 15, we swap them, resulting in the list [6, 1, 15, 22, 48].
• Compare the first element, 6, to the second element, 1. Since 1 is smaller than 6, we swap them, resulting in the final sorted list of [1, 6, 15, 22, 48].

Here is an illustration for you to have a better understanding of the sorting method.

Insertion sort algorithm

Here is the insertion sort algorithm implemented in Python:

def insert_srt(a):
  for k in range(1, len(a)):
    curr_val = a[k]
    x = k - 1
    while x >= 0 and a[x] > curr_val:
      a[x+1] = a[x]
      x -= 1
    a[x+1] = curr_val
  return a
Code language: Python (python)

To use the algorithm, call the insertion_sort function and pass in the list that you want to sort as an argument. For example:

srt_arr=[22,6,15,48,1]
print("List before insertion sort\n",srt_arr)
sort_list = insert_srt(srt_arr)
print("List after insertion sort\n",sort_list) Code language: Python (python)

This will return a new sorted list in ascending order. If you want to sort the list in descending order, you can modify the comparison operator in the while loop from > to <.

Click Here to try the above code by yourself.

Advantages and disadvantages of insertion sort

This algorithm in comparison with other sorting techniques, insertion sort also has more advantages and disadvantages.

Advantages of Insertion sort:

• Simple to understand and implement
• Efficient for small lists
• Can be used with partially sorted lists
• Provides stability, since it maintains the order of elements with the same value.

Disadvantages of Insertion sort:

• Inefficient for large lists (time complexity increases exponentially with the size of the list)
• Not suitable for lists with many duplicate elements
• Not adaptable to different data structures (works best with arrays)

Applications of insertion sort

Examples of where insertion sort is used in practice: Insertion sort is used in a variety of applications, including:

• Sorting a hand of playing cards according to the numbers and colors.
• Sorting shirts in a closet according to color and size by a tailor.
• Sorting a list of contact information in alphabetical order.
• Sorting the products on an e-commerce website from high to low price or low to high price.
• Sorting items in inventory systems by item names.
• Sorting a list of documents from high-priority to low-priority.
• Sorting elements in graphical user interfaces for a table or spreadsheet.
• Sorting data in databases by a specific field or attribute.

Conclusion

To conclude today’s article, we discussed the insertion sort technique, a sorting method used to sort the elements of an array in ascending order. It is a simple and efficient sorting algorithm for small lists. It is useful in a variety of applications, but it is important to consider its limitations and choose the appropriate algorithm for the task at hand. 

I hope you found my article helpful and that it made you one step closer to your coding journey. If you have any queries, you can comment them down below and I’ll be happy to answer them. We will be back again with another amazing article soon. Till then, keep coding, and have a great day ahead!