What Is the Insertion Sort in Data Structure Explain With a Suitable Example?
In computer science, sorting algorithms are essential tools for organizing and manipulating data efficiently. One such algorithm is the insertion sort.
This algorithm works by repeatedly inserting an element from an unsorted portion of the array into its correct position in the sorted portion. The process continues until all elements are in their proper place.
How Does Insertion Sort Work?
The insertion sort algorithm can be explained through the following steps:
- Start with an unsorted array of elements.
- Take the first element from the unsorted portion and insert it into its correct position in the sorted portion.
- Maintain a ‘sorted’ subarray to the left of the current element being considered.
- Compare the current element with each element in the sorted subarray, shifting them to the right if they are greater than the current element.
- Insert the current element into its correct position once a smaller element is encountered or when reaching the beginning of the sorted subarray.
- Repeat steps 2-5 for each remaining unsorted element until all elements are sorted.
An Example to Illustrate Insertion Sort
To better understand how insertion sort works, let’s consider an example:
Input: [9, 7, 5, 11, 12, 2, 14, 10]
Step 1: [9] (initially considered as sorted)
Step 2: [7,9]
Step 3: [5, 7, 9]
Step 4: [5, 7, 9, 11]
Step 5: [5, 7, 9, 11, 12]
Step 6: [2, 5, 7, 9, 11, 12]
Step 7: [2, 5, 7 ,9 ,10 ,11 ,12 ,14]
In the above example:
- The first element is already considered sorted because it has no preceding elements.
- In the second step, the number ‘7’ is compared with ‘9’. Since ‘7’ is smaller than ‘9’, it is inserted before ‘9’, resulting in the subarray [7,9].
- This process continues until all elements are sorted.
The Time Complexity of Insertion Sort
The time complexity of insertion sort depends on the input size. In the worst-case scenario (when the array is in reverse order), insertion sort has a time complexity of O(n^2). However, in average and best-case scenarios (when the array is already partially or fully sorted), insertion sort has a time complexity of O(n).
In conclusion, insertion sort is a simple yet effective sorting algorithm that works well for small input sizes or partially sorted arrays. It operates by repeatedly inserting an element from the unsorted portion into its correct position within the sorted portion. While not as efficient as some other sorting algorithms for large datasets, insertion sort remains a fundamental concept in computer science and data structures.