Insertion Sort

Unknown 16:55
Insertion Sort is the simplest sorting algorithm which sorts the array by shifting elements one by one.
It works the way we sort playing cards in our hands.
Characteristics:

  • Simple implementation.
  • Efficient for (quite) small data sets.
  • More efficient in practice than most other simple quadratic (i.e., O(n*n)) algorithms such as selection sort or bubble sort.
  • Stable; i.e., does not change the relative order of elements with equal keys.
  • In-place; i.e., only requires a constant amount O(1) of additional memory space.

EXAMPLE

[Reference: wikipedia]

INSERTION SORT C-CODE

// C program to implement Insertion sort
#include <stdio.h>
 int main()
{
    int arr[] = {6, 3, 5, 2, 8, 10, 9};
    int n = sizeof(arr)/sizeof(arr[0]);
    int i, j, key;
    //Insertion Sort starts
    for (i = 1; i < n-1; i++)      
    {
         key=arr[i];
         for (j = i - 1; j >= 0 && arr[j] > key; j--)
         {
              a[j + 1] = arr[j];
          }
          arr[j + 1] = key;
    }
    //Insertion Sort ends
    printf("Sorted array: \n");
    for (int i=0; i < n; i++)
    {
        printf("%d ", arr[i]);
    }
    return 0;
}
OutputSorted array:
2  3  5  6  8  9  10

COMPLEXITY ANALYSIS

  • Worst and Average Case Time Complexity: O(n*n). Worst case occurs when array is reverse sorted.
  • Best Case Time Complexity: O(n). Best case occurs when array is already sorted.
  • Auxiliary Space Complexity: O(1). Only single extra memory space is required for "key" variable.
Tags: