Insertion Sort Algorithm

 Sorting is the process of arranging a list of elements in a particular order (Ascending or Descending).

Insertion sort algorithm arranges a list of elements in a particular order. In insertion sort algorithm, every iteration moves an element from unsorted portion to sorted portion until all the elements are sorted in the list.

Step by Step Process

The insertion sort algorithm is performed using the following steps...

• Step 1 - Assume that first element in the list is in sorted portion and all the remaining elements are in unsorted portion.
• Step 2: Take first element from the unsorted portion and insert that element into the sorted portion in the order specified.
• Step 3: Repeat the above process until all the elements from the unsorted portion are moved into the sorted portion. 

Insertion Sort Logic

  for (i = 1 ; i <= n - 1; i++)
    {
	    j = i;
            while ( j > 0 && arr[j-1] > arr[j])
            {	        
                temp     = arr[j];
                arr[j]   = arr[j-1];
                arr[j-1] = temp;
                j--;
            }
    }

Example

 

Implementation of Insertion Sort Algorithm using C Programming Language

 

#include <stdio.h>
int main()
{
    int n, i, j, temp;
    int arr[64];
 
    printf("Enter the number of elements to be sorted: ");
    scanf("%d", &n);
    for (i = 0; i < n; i++)
    {
        printf("Enter element no. %d: ", i+1);
        scanf("%d", &arr[i]);
    }
    for (i = 1 ; i <= n - 1; i++)
    {
        j = i;
            while ( j > 0 && arr[j-1] > arr[j])
            {           
                temp     = arr[j];
                arr[j]   = arr[j-1];
                arr[j-1] = temp;
                j--;
            }
    }
    printf("Sorted list in ascending order:\n");
    for (i = 0; i <= n - 1; i++)
    {
         printf("%d  ", arr[i]);
    }
    return 0;
}

 

Output