FOR FREE CONTENT

Insertion Sort

Back to Programming

Description

The word ‘Sorting’ means arranging the elements in either ascending or descending order. The insertion sort is a simple sorting technique that is based on the principle of insertion of any element in the required position i.e. the sorting is done in such a way it seems like the new element is inserted at its sorted position at that particular time which makes this sorting technique different from ‘bubble sort’ or ‘selection sort’. If there is n number of elements then it will require n-1 iterations to sort the elements.

PROCEDURE WITH EXAMPLE:

Suppose there are 5 elements in an array as below and we want to sort them in ascending order. As the number of elements is 5 then it will need 5 - 1 = 4 steps to sort the array. The first cell is containing the element ‘12’. If we imagine the array with only one element ‘12’ then it need not be sorted.

From the second element, the sorting will be taken place and the steps are as follows:

Step-1:

In this step consider that the new element ‘54’ has to be inserted into the array. So first the element ‘54’ is compared with the previously existing element ‘12’ but as it is already in a sorted order so no shifting of elements will be needed.

Step-2:

Similar to Step 1, here also 65 is inserted in its sorted position which does not need any shifting of elements as it is greater than both ‘54’ and ’12’.

Step-3:

Now the new element is ‘32’ which is to be inserted in the array. Before inserting it when it is compared to its previous element ‘65’ it is fount that ‘32’ is lesser than ‘65’ so the element ‘65’ is shifted to its one position right. Then again it is compared to ‘54’ which is also greater than ‘32’ so that ‘54’ is also shifted to its one position right and the array will look like below before positioning ‘32’ into its proper position.

After this the element ‘32’ will be inserted in its current sorted position and the array will be:

Step 4:

The last element to be inserted into the array is ‘9’. Similar to Step 3, the element ‘9’ will be compared with ‘65’ which is greater than ‘9’ so it will be shifted one position right, again it will be compared with ‘54’ and as ‘54’ is also greater than ‘9’ it will also be shifted one position right. Similarly as both ‘32’ and ’12’ is also greater than 9 they will also be shifted in a similar way and the array will look like below before positioning the element ‘9’.

After this, the element will be positioned and the final sorted array will look like this:

Algorithm

INPUT:An unsorted array arr[6,2,4,1,…………….,n]
OUTPUT:An sorted array arr[1,2,3,4,5,…………..,n] (in ascending order)
PROCESS:
Step 1: [Taking the number of elements and the array elements in the array ]
   Read n
   For i=0 to n
	 Read arr[i]

Step 2: [Sorting the elements of the array ]
    Step 2.1: For i=1 to n-1repeat Step 2.2 to Step 2.5
	Step 2.2: Set   t <- arr[i]
	Step 2.3: For j=i-1 to 0 repeat Step 2.4
	Step 2.4: If(t<arr[j]) then 
       Set  arr[j+1] <- arr[j]
		 [End of ‘If’]
		   Else  
             break
		[End of ‘Else’]
		[End of Step 2.3 ‘For’ loop]
	Step 2.5: Set  arr[j+1] <- t	
[End of Step 2.1 ‘For’ loop]

Step 3: [Display the sorted array]
	For i=0 to n
		Display (arr[i])
	End For loop

Step 4: Stop

Code

CHARACTERISTICS:

1. It works well for small data sets.

2. Insertion sort is an adaptive sorting technique.

3. The sorting technique is stable.

4. It is a comparison-based sorting technique.

5. It is an online sorting technique and requires a constant amount of memory spaces to be sorted.

APPLICATION:

1. It is used to sort a small set of data.

2. Insertion sort works very fast and well if some of the elements are already sorted.

3. In any other sorting technique, it can be used to sort a sub-array or sub-list to reduce the number of comparisons needed in recursion.

ADVANTAGES:

1. Works better than quick sort for small amount data.

2. It is an in-place algorithm.

3. Space complexity is O(1) which is constant and best case time complexity is O(n).

4. It is also called an efficient sort.

DISADVANTAGES:

1. It is not an efficient algorithm for a large number of elements.

2. Though the best case complexity is better than the bubble or selection sort but worse than the merge sort or quick sort.

TIME COMPLEXITY:

Best case:

The best-case complexity occurs if the array elements are already sorted. In case of insertion sort algorithm if the array is already sorted, for example, {1,2,3,4,5} is the array then whenever a new element is to be inserted only it is compared to its immediate left element i.e. only one comparison will be needed for each iteration.

Hence, the total number of comparisons for n elements:

Average case:

Average case complexity means that the algorithm takes the average time or steps to be completed. In case of insertion sort, the average case can be considered while it needs (n - 1)/2 comparisons in the inner loop for inserting a new element into the array i.e. while the new element will be inserted into the middle position of the sorted array.

Hence, the total number of comparisons for n elements:

Worst case:

The worst-case complexity occurs if the array elements are in reverse order. In that case for each ith element, the number of comparisons needed will be i - 1 i.e. for the 2nd element the number of comparisons will be 1, for the 3rd element the number of comparisons will be 2, and so on.

Hence, the total number of comparisons for n elements:

SPACE COMPLEXITY:

Please Login to Bookmark