In this tutorial, we will explore the inner workings of the Insertion Sort algorithm in data structure. Insertion Sort is a simple yet efficient sorting algorithm that works by repeatedly inserting an element from an unsorted portion of the list into its correct position in a sorted portion. It is an in-place comparison-based sorting algorithm that has an average and worst-case time complexity of O(n^2).
How Does Insertion Sort Work?
The basic idea behind Insertion Sort is to divide the input list into two portions: a sorted portion and an unsorted portion. Initially, the sorted portion contains only the first element of the list, and the rest of the elements are considered part of the unsorted portion.
To sort the list, we iterate through each element starting from the second element (index 1) until we reach the end of the list. For each iteration, we compare the current element with all elements in its left-hand side (i.e., elements in the sorted portion) until we find its correct position.
To insert an element at its correct position, we shift all larger elements one position to the right until we find a smaller or equal element or reach the beginning of the list. Once we find such an element, we insert our current element at that position.
Example:
Let’s understand how Insertion Sort works with a simple example:
- Step 1: Consider a list: [5, 2, 4, 6, 1, 3]
- Step 2: Start with index 1 (the second element):
- Iteration 1:
- Current element: 2
- Compare with elements in the sorted portion (5):
- 2 < 5, so we insert 2 at index 0:
- List after insertion: [2, 5, 4, 6, 1, 3]
- Iteration 2:
- Current element: 4
- Compare with elements in the sorted portion (2, 5):
- 4 > 2 and 4 = 5, so we insert 4 at index 1:
- List after insertion: [2, 4, 5, 6, 1, 3]
This process continues until we reach the end of the list. At each iteration, the sorted portion grows by one element. Eventually, all elements are part of the sorted portion and the list is fully sorted.
Advantages and Disadvantages of Insertion Sort:
The main advantage of Insertion Sort is its simplicity. It is easy to understand and implement compared to more complex sorting algorithms like Quicksort or Merge Sort.
However, Insertion Sort is not suitable for sorting large lists or lists with a random order. Its time complexity of O(n^2) makes it inefficient for large datasets. In such cases, algorithms like Quicksort or Merge Sort are preferred.
Despite its limitations, Insertion Sort performs well on small lists or partially sorted lists. It is also an excellent choice for sorting elements as they are being received in real-time since it can efficiently maintain a sorted portion while new elements are added.
Conclusion:
In this tutorial, we explored the Insertion Sort algorithm in data structure. We learned how it works by repeatedly inserting elements from the unsorted portion into their correct positions in the sorted portion.
Although Insertion Sort has some limitations, it is a simple and efficient sorting algorithm for small or partially sorted lists. Understanding its inner workings can help us appreciate the broader concepts of sorting algorithms and their applications.