Straight Insertion Sort using C

 Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time.

 

Let’s say we have an array a, so at each i-th pass, a[i] is successively compared with a[i-1], a[i-2], etc. until an element smaller than a[i] is found or the beginning of the array is reached. Elements that are found to be greater than a[i], are moved right by one position each to make room for a[i].

The time complexity of this algorithm is O(n^2).

The complete source code is given below

/* 
 * File:   StraightInsertionSort.c
  */

#include <stdio.h>
#include <stdlib.h>

void straightInsertionSort(int a[], int n) {
    int i = 1, j, k = 0;
    int temp;
    while (i < n) {
        j = i - 1;
        temp = a[j + 1];
        k = i;
        while (j >= 0) {
            if (temp < a[j]) {
                k = j;
                j--;
            } else {
                break;
            }
        }
        j = i;
        while (j > k) {
            a[j] = a[j - 1];
            j--;
        }
        a[j] = temp;
        i++;
    }
    printf("\n");
    printf("\nThe sorted array elements are given below\n");
    for (i = 0; i < n; i++) {
        printf("a[%d]=%d ", i, a[i]);
    }
}

int main() {
    int i, n = 6;
    int a[] = {15, 8, 17, 12, 38, 19};
    printf("\n:: Straight Insertion Sort ::\n");
    printf("\nInput array elements\n");
    for (i = 0; i < n; i++) {
        printf("a[%d]=%d ", i, a[i]);
    }
    straightInsertionSort(a, n);
}

Output

:: Straight Insertion Sort ::

Input array elements
a[0]=15 a[1]=8 a[2]=17 a[3]=12 a[4]=38 a[5]=19 

The sorted array elements are given below
a[0]=8 a[1]=12 a[2]=15 a[3]=17 a[4]=19 a[5]=38