What Is Insertion Sort Algorithm in Data Structure?
When it comes to sorting elements in a list or an array, there are several algorithms available. One such algorithm is the Insertion Sort algorithm. It is a simple yet efficient sorting technique that works well for small lists or arrays.
How does the Insertion Sort algorithm work?
The Insertion Sort algorithm works by dividing the list into a sorted and an unsorted section. Initially, the sorted section contains only the first element of the list, while the remaining elements are considered part of the unsorted section.
The steps involved in performing an insertion sort are as follows:
- Start with the second element (index 1) of the list.
- Compare this element with all previous elements in the sorted section.
- If any element is greater than the current element, shift it one position to the right.
- Continue this process until you find an element that is smaller than or equal to the current element.
- Insert the current element at its correct position in the sorted section.
- Repeat steps 2-5 for all remaining unsorted elements until the entire list is sorted.
To better understand how insertion sort works, let’s consider an example. Suppose we have an array [5, 2, 4, 6, 1, 3].
We start with index 1 (element ‘2’) and compare it with index 0 (element ‘5’). Since ‘2’ is smaller than ‘5’, we shift ‘5’ one position to the right and insert ‘2’ at index 0. The updated array becomes [2, 5, 4, 6, 1, 3].
Next, we move to index 2 (element ‘4’) and compare it with elements in the sorted section ([2, 5]). We find that ‘4’ is smaller than ‘5’, so we shift ‘5’ one position to the right and insert ‘4’ at index 1. The updated array becomes [2, 4, 5, 6, 1, 3].
We repeat this process for all remaining unsorted elements until the entire array is sorted. In this example, the final sorted array will be [1, 2, 3, 4, 5, 6].
The time complexity of the Insertion Sort algorithm is O(n^2), where n is the number of elements in the list. This means that as the number of elements increases, the time taken to sort them grows exponentially.
However, despite its higher time complexity compared to some other sorting algorithms like Quick Sort or Merge Sort (which have an O(n log n) time complexity), Insertion Sort performs well for small lists or arrays due to its simplicity and low space complexity.
Insertion Sort is a simple yet efficient algorithm for sorting elements in a list or an array. It works by dividing the list into a sorted and an unsorted section and gradually inserting each element from the unsorted section into its correct position in the sorted section.
Although it may not be as fast as some other sorting algorithms for large datasets due to its O(n^2) time complexity, Insertion Sort is still widely used in practice for smaller datasets where simplicity and space efficiency are important factors.