Insertion Sort is a sorting algorithm that picks and places one element at a time in its right position by comparing and shifting them.

Steps

Insertion Sort in Data Structure and Algorithm - DSA
  • Start loop for 1 to the length of array - i
    • Key - Pick an element from the array which is at index i
    • j will be i-1
    • Run while loop until j>=0 and array element at j>key
      • Compare with all elements in the sorted sub-list
      • Shift all the elements in the sorted sub-list that is greater than the value to be sorted
    • After while loop is completed, Insert the key at j+1

Code

#include <stdio.h>

void swap(int *x, int *y){
    int temp = *x;
    *x = *y;
    *y = temp;
}

void printArray(int arr[], int n){
    for (int i = 0; i < n; i++){
        printf("%d ", arr[i]);
    }
}

void insertitionSort(int arr[], int n){
    for (int i = 1; i < n; i++){
        int key = arr[i]; // Value to be place at right position
        int j = i - 1; // J for left side comparing array left side of temp
        while (j >= 0 && arr[j] > key){
            arr[j + 1] = arr[j]; // Shifting array one step right
            j--;
        }
        arr[j + 1] = key; // Placing element to right position
    }
}

void main(){
    int arr[] = {5,4,2,3,1};
    int n=5;
    insertitionSort(arr, n);
    printArray(arr, 5);
}