Apex Algorithm : Insertion Sort

Topics to be Covered:

1. Why learning sorting algorithms is important?
2. What is insertion Sort?
3. Explanation of code?
4. Pseudocode and real time code
5. Time Complexity for insertion sort: Worst Case, Best Case and Average Case

Why learning sorting algorithms is important?

Sorting is a fundamental operation in computer science. As a result, we have a large number of good sorting algorithms. Understanding different sorting algorithms strengthen our core.

What is Insertion Sort?

Insertion sort works in the similar way as we sort cards in our hand in a card game.

We assume that the first card is already sorted then, we select an unsorted card. If the unsorted card is greater than the card in hand, it is placed on the right otherwise, to the left. In the same way, other unsorted cards are taken and put at their right place.

A similar approach is used by insertion sort.

Consider the following array: 12, 11, 13, 5, 6

First Iteration: Compare 12 with 11. The comparison shows 11< 12. Hence swap 11 and 12.

The array now looks like:

11, 12, 13, 5, 6

Second Iteration: Begin with the second element (12), but it was already swapped on for the correct position, so we move ahead to the next element.

Now hold on to the third element (13) and compare with the ones preceding it.

Since 13>12, no swapping takes place.

Also, 13> 11, no swapping takes place and 13  remains at its position.

The array after the Second iteration looks like:

11,12,13,5,6

Third Iteration: Start the following Iteration with the fourth element (5), and compare it with its preceding elements.

Since 5< 13, we swap the two.

Array now becomes: 11, 12, 5, 13, 6

But there still exist elements that we haven’t yet compared with 5. Now the comparison takes place between 12 and 5. Since, 5 < 12, we swap the two.

The array becomes 11, 5, 12, 13, 6

The last comparison for the iteration is now between 11 and 5. Since 5 < 11, we swap the two.

The array now becomes 5, 11, 12, 13, 6

Fourth Iteration: The last iteration calls for the comparison of the last element (2), with all the preceding elements and make the appropriate swapping between elements.

Since, 6< 13. Swap 6 and 13.

Array now becomes: 5, 11, 12, 6, 13.

Compare 6 with 11, 12, 5.

Since, 6< 12. Swap 6 and 12.

5, 11, 6, 12, 13.

Compare 6 with 11 and 5.

Since, 6<11. Swap 6 and 11.

Array now becomes:

5, 6, 11, 12, 13.

The last comparison for the Iteration is to compare 6 with 5.

Since 6 >5. No Swapping 2

The array now becomes:

5, 6, 11, 12, 13

Pseudocode

INSERTION-SORT(A)
   for i = 1 to n
   	key ← A [i]
    	j ← i – 1
  	 while j > = 0 and A[j] > key
   		A[j+1] ← A[j]
   		j ← j – 1
   	End while 
   	A[j+1] ← key
  End for

Actual Code for Insertion Sort

List<integer> l1 = new List<integer>{12, 11, 13, 5, 6};         
    for (integer i = 1; i < l1.size(); i++) { 
            integer key = l1[i];
        //j is initially 0th index
            integer j = i - 1; 
  
            while (j >= 0 && l1[j] > key) { 
             // moving the left side element to one position forward.
                l1[j + 1] = l1[j];
                j = j - 1; 
            } 
            l1[j + 1] = key; 
            system.debug(l1);
        } 

Time Complexities

• Worst Case Complexity: O(n^2)Suppose, an array is in ascending order, and you want to sort it in descending order. In this case, worse case complexity occurs.Each element has to be compared with each of the other elements so, for every nth element, n-1 number of comparisons are made.Thus, the total number of comparisons = n*(n-1) ~ n2
• Best Case Complexity: O(n)When the array is already sorted, the outer loop runs for n number of times whereas the inner loop does not run at all. So, there is only n number of comparison. Thus, complexity is linear.
• Average Case Complexity: O(n^2)It occurs when the elements of a array are in jumbled order (neither ascending nor descending).

Space Complexity

Space complexity is O(1) because an extra variable key  is used.

Insertion Sort Applications

The insertion sort is used when:

• the array is has a small number of elements
• there are only a few elements left to be sorted

Together we can learn faster

You can join the Whatsapp group 

You can join Facebook group

You can join Twitter

You can join Instagram