What Is Insertion Sort in Data Structure With Example?
Insertion sort is a simple sorting algorithm that is widely used in computer science. It works by taking one element at a time and placing it in its correct position within the already sorted portion of the array.
This process is repeated until all elements are sorted.
How Does Insertion Sort Work?
The insertion sort algorithm starts by considering the second element of the array. It compares this element with the first element and swaps them if necessary to ensure that they are in the correct order.
The algorithm then moves on to consider the third element and inserts it into its correct position among the first three elements. This process continues until all elements have been inserted into their appropriate places.
Example:
Let’s illustrate how insertion sort works with an example. Consider an array of numbers: [5, 3, 8, 4, 2].
We will go through each step of the algorithm to demonstrate how it sorts this array.
Step 1:
- 5, 3, 8, 4, 2 – The first two elements are already sorted.
Step 2:
- 3, 5, 8, 4, 2 – The third element (8) is greater than the previous two elements (3 and 5), so it remains in place.
Step 3:
- 3, 5, 8, 4, 2 – The fourth element (4) is smaller than the previous three elements (3, 5, and 8). It needs to be placed before them.
Step 4:
- 3, 4, 5, 8, 2 – The fifth element (2) is smaller than all the previous elements. It needs to be placed at the beginning of the array.
After completing all the steps, the array becomes [2, 3, 4, 5, 8], which is now sorted in ascending order.
Complexity Analysis:
The average and worst-case time complexity of insertion sort is O(n^2), where n is the number of elements in the array. However, in best-case scenarios where the array is already sorted or nearly sorted, insertion sort has a time complexity of O(n).
In terms of space complexity, insertion sort requires only a constant amount of additional space because it operates directly on the input array.
Conclusion:
Insertion sort is a straightforward sorting algorithm that works well for small input sizes or partially sorted arrays. Despite its simplicity, it can be quite efficient in certain cases.
By understanding how insertion sort works and analyzing its time complexity, you can make informed decisions about when to use this sorting algorithm.