Insertion Sort

2.2K

Insertion sort is the most generic example of a sorting algorithm, and the one which is used by one of the most naive users. Often we must have also used this algorithm in our real life examples unknowingly. One of the favorite example is:-

This is a very common scenario and we must have used it. Suppose you get a hand of cards. Our general approach is that we start scanning the cards from starting and if we find a card out of place, we remove it from there and start looking from the beginning and insert it at the right place.

STEPS:

Suppose our cards are arranged like 2, 4, 6, 3, 10, K, J. The steps we follow would be:-

• Start scanning the cards. 2 is correct, 4 is correct, 6 is correct. 3 is NOT correct. It does not follow the ascending order.
• Now we need to insert 3 at the right place.
• Pick up card 3 and start scanning from the beginning. 3 is greater than 2, so move ahead. 3 is less than 4, so INSERT the card 3 before 4. Now our hand is 2, 3, 4, 6, 10, K, J.
• Now again start scanning the cards from where we left off. 6 is at right place, 10 is at right place, K is at right place. J is not at right place, because it is not following the ascending order rule.
• Pick up card J and start scanning form the beginning. J is greater than 2, 3, 4, 6, 10. But J is less than K, so INSERT the card J before K.

Now our sorting is finally complete and thus, the hand we have is:- 2, 3, 4, 6, 10, J, K. We INSERTED the cards in the middle and hence this type of sorting gets its name INSERTION SORT.

ALGORITHM:

Now we can devise an algorithm for this sorting technique.

1. Start scanning the elements from 2nd position. The 1st is assumed to be at correct place.
2. if ( arr[i] < arr[i-1])
   • Swap arr[i] and arr[i-1]
   • Keep swapping until the number is less than the previous number
3. The array gets sorted as we reach the end.

Here is a working implementation of the same.

#include<stdio.h>;

// function to swap two integers
void swap(int *x, int *y)
{
    int temp = *x;
    *x = *y;
    *y = temp;
}

// a function to perform Insertion Sort on the array arr with size specified
void insertionSort(int arr[],int size)
{
    int i,j;

    // iterating from 2nd element to the last
    for(i = 1; i < size; i++)
    {
        if(arr[i] < arr[i-1])
        {
            j = i;
            while(arr[j-1] < arr[j])
            {
                // swapping all the numbers
                // until the next number is smaller than previous number
                swap(&arr[j], &arr[j-1]);
                j--;
            }
        }
    }
}

// driver function to test the above function
int main(void)
{
    int i;
    int arr[10] = {3, 4, 7, 1, 10, 8, 2, 22, 99, 50};

    insertionSort(arr,10);

    printf("SORTED array:- ");
    for(i = 0; i < 10; i++)
        printf("%d ",arr[i]);

    return 0;
}
Code language: C/AL (cal)

Running Time:-
Average Case:- O(n²)
Best Case:- O(n)
Worst Case:- O(n²)

Video Explanation: