What Is the Insertion Sort in Data Structure Explain With Suitable Example?

What Is the Insertion Sort in Data Structure Explain With Suitable Example?

The insertion sort is a simple sorting algorithm that works by repeatedly inserting elements into a sorted sublist, making it gradually larger until the entire list is sorted. It is an efficient algorithm for small data sets or for lists that are almost sorted.

How Does Insertion Sort Work?

The insertion sort algorithm builds the final sorted array one item at a time. It assumes that the first element in the list is already sorted. Then, for each subsequent element, it compares it with the elements in the sorted sublist and inserts it into its correct position in the sublist.

Here’s how the insertion sort algorithm works:

1. Step 1: Assume the first element is already sorted.
2. Step 2: Take the next element and compare it with all elements in the sorted sublist.
3. Step 3: Shift all the elements greater than the current element to one position ahead to make space for inserting.
4. Step 4: Insert the current element into its correct position in the sublist.
5. Step 5: Repeat steps 2 to 4 until all elements have been processed.

An Example of Insertion Sort

To better understand how insertion sort works, let’s consider an example. Suppose we have an array of integers: [5, 3, 8, 4, 2].

We start with assuming that the first element (5) is already sorted. Then we move on to the next element (3) and compare it with the sorted sublist [5].

Since 3 is smaller than 5, we shift 5 one position ahead and insert 3 into the first position. The updated array becomes [3, 5, 8, 4, 2].

Next, we compare the third element (8) with the sorted sublist [3, 5]. Since 8 is greater than both elements in the sublist, it remains in its current position.

We continue this process for the remaining elements. After comparing and shifting as necessary, we insert the last element (2) into its correct position. The final sorted array becomes [2, 3, 4, 5, 8].

Time Complexity of Insertion Sort

The time complexity of insertion sort is O(n^2) in the worst-case scenario when the list is in reverse order. However, it performs quite well for small data sets or nearly sorted lists with a best-case time complexity of O(n).

Overall, insertion sort is a simple yet effective sorting algorithm that can be easily implemented and understood. It is particularly useful for small lists or partially sorted data.