Simple Insertion Sort Program using functions in C


Definition

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages like simple implementation, efficient for (quite) small data sets, more efficient in practice than most other simple quadratic algorithms, adaptive, stable, in-place; i.e., only requires a constant amount of additional memory space, online; i.e., can sort a list as it receives it

Simple Insertion Sort Program using functions

/* Simple Insertion Sort Program Using Functions in C*/
/* Data Structure Programs,C Array Examples */

#include<stdio.h>
#include<conio.h>

#define MAX_SIZE 5

void insertion(int[]);

int main() {
    int arr_sort[MAX_SIZE], i;

    printf("Simple Insertion Sort Example - Array and Functions\n");
    printf("\nEnter %d Elements for Sorting\n", MAX_SIZE);
    for (i = 0; i < MAX_SIZE; i++)
        scanf("%d", &arr_sort[i]);

    printf("\nYour Data   :");
    for (i = 0; i < MAX_SIZE; i++) {
        printf("\t%d", arr_sort[i]);
    }

    insertion(arr_sort);
    getch();
}

void insertion(int fn_arr[]) {
    int i, j, a, t;
    for (i = 1; i < MAX_SIZE; i++) {
        t = fn_arr[i];
        j = i - 1;

        while (j >= 0 && fn_arr[j] > t) {
            fn_arr[j + 1] = fn_arr[j];
            j = j - 1;
        }
        fn_arr[j + 1] = t;

        printf("\nIteration %d : ", i);
        for (a = 0; a < MAX_SIZE; a++) {
            printf("\t%d", fn_arr[a]);
        }
    }

    printf("\n\nSorted Data :");
    for (i = 0; i < MAX_SIZE; i++) {
        printf("\t%d", fn_arr[i]);
    }
}

Sample Output:

Simple Insertion Sort Example - Array and Functions

Enter 5 Elements for Sorting
901
56
34
23
2

Your Data   :   901     56      34      23      2
Iteration 1 :   56      901     34      23      2
Iteration 2 :   34      56      901     23      2
Iteration 3 :   23      34      56      901     2
Iteration 4 :   2       23      34      56      901

Sorted Data :   2       23      34      56      901

------------------
(program exited with code: 0)

Press any key to continue . . .