Program Code

#include 

/**
 * Function to perform insertion sort on an array.
 * @param arr: Array to be sorted
 * @param n: Size of the array
 */
void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) { int key = arr[i]; int 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--;
        }
        arr[j + 1] = key;
    }
}

/**
 * Function to print the array.
 * @param arr: Array to be printed
 * @param n: Size of the array
 */
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

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;
}

Program Structure Explanation

This C program demonstrates the insertion sort algorithm, which sorts an array by building a sorted section one element at a time. The main components of the program are as follows:

1. Header Files: The program includes the standard input-output library #include <stdio.h> for using the printf function.
2. Insertion Sort Function:
   • The insertionSort function takes an integer array arr and its size n.
   • A loop iterates through the array starting from the second element. For each element, it stores the value in key and finds the correct position for it in the sorted part of the array.
   • Elements greater than key are moved one position ahead to make space for the key.
3. Print Array Function:
   • The printArray function takes an array and its size, iterating through the array to print each element.
4. Main Function:
   • Declares and initializes an array of integers to be sorted.
   • Calculates the size of the array and prints the original array.
   • Calls the insertionSort function to sort the array.
   • Prints the sorted array.

Conclusion

The insertion sort algorithm is efficient for small datasets and works by building a sorted array one element at a time. This program provides a clear example of how insertion sort can be implemented in C, demonstrating both the sorting logic and the structure of a simple C program.