C Program to Implement Insertion Sort

1. Introduction

Insertion Sort is a simple and intuitive sorting algorithm. It builds the final sorted array one item at a time. The algorithm works similarly to how you might sort playing cards in your hands: you take one card at a time and insert it in the right position.

2. Program Overview

In this program, we will:

1. Create a function to implement the Insertion Sort algorithm.

2. Sort an array of integers using Insertion Sort.

3. Display the sorted array.

3. Code Program

#include <stdio.h>

// Insertion Sort function
void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];  // Take the current element
        j = i - 1;

        // Move elements of arr[0...i-1] that are greater than key to one position ahead of their current position
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

// Function to print an array
void printArray(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

// Driver code
int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Original array: \n");
    printArray(arr, n);

    insertionSort(arr, n);

    printf("Sorted array: \n");
    printArray(arr, n);
    return 0;
}

Output:

Original array:
12 11 13 5 6
Sorted array:
5 6 11 12 13

4. Step By Step Explanation

1. The insertionSort function works by iterating over the array from the second element to the last.

2. For each element (called a key), it compares the element with the previous elements. If the key element is smaller than the previous element, the previous elements are moved up to make space for the key.

3. This process is repeated until the correct position for the key is found, and then the key is inserted in its correct position.

4. This is repeated for all the elements in the array, leading to a sorted array at the end.

5. The printArray function is a utility function to display the elements of an array.

6. The main function initializes an array, prints it, sorts it using insertion sort, and then prints the sorted array.

Insertion sort is efficient for smaller datasets and partially sorted arrays but may not be suitable for larger datasets.