Insertion Sort || Sorting Algorithms

What is the need for Sorting?

Imagine you are given a task to find a specific type of key from a huge pile of keys. The process will be complex and time-consuming. Right. Now Imagine, that pile of keys is sorted and labeled, like Small keys are in one zone and rest in another. Similarly, searching in huge data can be complex and Time-Consuming. Hence, Sorting is Preferred(whenever possible) so that any use to data can be done in a very less span of time.

Secondly, when we have to merge to set of data if the data are already sorted separately, then merging can be done very easily and most importantly very efficiently.

Types of Sorting Algorithms?

Some of the Most Common Types of Sorting Algorithms include:

· Bubble Sort

· Quick Sort

· Selection Sort

· Merge Sort

· Insertion Sort

· Etc.

Insertion Sort

Insertion Sort is one of the simplest sorting Algorithms Available. It is Quite Similar to the Physical Sorting Techniques that we use in day-to-day life and hence it is easier to understand also. Like if we have a pile of objects or a set of cards and we want to sort them. We would take the available element or the object/cards and put them in the desired order to sort them. The same is with Insertion Sort. We traverse through the array. When we find an element at the wrong position, we insert it at the current position and continue checking the rest of the elements.

Being the easiest to understand Sorting Algorithm, this algorithm would take the maximum time to sort an array if the array is already sorted in the opposite order.

The Time Complexities in the Case of Insertion Sort is as follows:

Best Case: Ω( n )

Worst Case: Θ(n²)

Average: O(n² )

Pseudo Code for insertion sort is as follows:

For i = 1 to array.length

Key = array[ i ]

j = i - 1

While i > 0 and arr[ j ] > key

Array[i + 1] = array[ j ]

j + = 1

array[ j + 1 ] = key

Insertion Sort Implementation in C++ Language:

#include <iostream>

using namespace std;

void insertion_sort( int arr[] ){

int temp;

for (int i = 1 ; i < 5 ; ++i ) {

temp = arr[i];

int j = i — 1 ;

while (j >= 0 && arr[j] > temp) {

arr[ j + 1 ] = arr[j];

j — = 1 ;

}

arr[ j + 1 ] = temp;

}

}

int main() {

int arr[] = {9,5,7,3,4};

cout << “ Unsorted Array : “ ;

for(int i = 0 ; i < 5 ; ++i ) {

cout << arr[ i ] << “ “ ;

}

Cout << endl;

insertion_sort( arr );

cout << “ Sorted Array : “ ;

for(int i = 0 ; i < 5 ; ++i ) {

cout << arr[ i ] << “ “ ;

}

}

Insertion Sort Working Explanation:

Let us assume that The Unsorted Array is

9, 5, 7, 3, 4

First Iteration

In the first Iteration, we compare 5 with the previous elements. Which is 9 in this case, so we will compare 5 with 9. Since 5 is smaller than 5, 5 will be inserted in the first location.

So, the array after the first iteration will be :

5, 9, 7, 3, 4

Second Iteration

In the Second Iteration, we will compare 7 will all the previous elements that are 5 and 9 in this case. Since 7 is smaller than 9 but is greater than 5. So, 7 will be inserted after 5 but before 9. 7 will be inserted in the second position.

So, the final array after Second Iteration will become :

5, 7, 9, 3, 4

Third Iteration

In the Third Iteration, we will compare 3 with all the previous elements that are 5, 7, and 9.

Since 3 is the smallest of all the Available elements hence we will insert 3 at the very starting of the array and after this iteration, the final array will be :

3, 5, 7, 9, 4

Fourth Iteration

In the Fourth Iteration, we will compare the last element with all the previous elements, which are 3,5,7, and 9 in this case. Now, 4 is smaller than 5,7, and 9 but is bigger than 3. So, 4 will be inserted in the 2nd position.

Now, the final array after this last iteration will become :

3, 4, 5, 7, 9

Now, this the final sorted array, in the increasing order.

Comparing Time Complexity of Insertion Sort with Other Sorting Algorithms

Time Complexity in Best Case

Insertion Sort: Ω( n )

Quick Sort: Ω( n log(n) )

Selection Sort: Ω( n² )

Merge Sort: Ω( n log(n) )

Bubble Sort: Ω( n )

Time Complexity in Worst Case

Insertion Sort: θ( n² )

Quick Sort: θ(n log( n ))

Selection Sort: θ( n² )

Merge Sort: θ(n log( n ))

Bubble Sort: θ( n² )

Average Time Complexity

Insertion Sort: O( n² )

Quick Sort: O( n² )

Selection Sort: O( n² )

Merge Sort: O(n log( n ))

Bubble Sort: O( n² )

Comparing Worst-Case Space Complexity of Insertion Sort with Other Sorting Algorithms

Insertion Sort: O( 1 )

Quick Sort: O( n log n )

Selection Sort: O( 1 )

Merge Sort: O( n )

Bubble Sort: O( 1 )

Conclusion

The Main Advantage of Insertion Sort lies in its straightforwardness. It exhibits a good performance when working with a small set of data. This Algorithm is an in-place sorting algorithm which means that this algorithm does not require any additional/auxiliary space.

This Algorithm’s biggest disadvantage is that in case the data is huge and reversed/unsorted them it is one of the slowest sorting algorithms.

This Disadvantage of Insertion Sort is one of the biggest reasons why coders do not prefer using this algorithm. But for students and new coders, this is generally the first algorithm that they understand in one go.