Understanding Insertion Sort Algorithm in C: Explained with Code

In this article, we'll discuss the Insertion Sort algorithm and its implementation in the C programming language. We'll provide a step-by-step explanation of the code along with examples.

Code Explanation:

Let's break down the provided C code:

insertionSort Function:

This function performs the Insertion Sort algorithm.


// Function to perform insertion sort
void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        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;
    }
}

The insertionSort function takes an integer array arr and its size n as parameters. It iterates through each element of the array and inserts it into the correct position in the sorted subarray to its left.

printArray Function:

This function prints the elements of an array.


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

The printArray function takes an integer array arr and its size n as parameters. It iterates through the array and prints each element, followed by a space, and then moves to the next line.

Main Function:

This is the main function where we declare an array, sort it using Insertion Sort, and print the sorted array.


// Main function
int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Array before sorting: \n");
    printArray(arr, n);

    insertionSort(arr, n);

    printf("Array after sorting: \n");
    printArray(arr, n);

    return 0;
}

In the main function, we declare an integer array arr with some initial values and its size n. We then print the array before sorting using the printArray function. After that, we call the insertionSort function to sort the array. Finally, we print the sorted array using the printArray function.

Understanding sorting algorithms like Insertion Sort is essential for any programmer, as sorting is a common task in many applications.

Insertion Sort Explanation:

Insertion sort is a simple sorting algorithm that works similarly to the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed in the correct position in the sorted part.

Working of Insertion Sort Algorithm:

To sort an array of size N in ascending order, iterate over the array and compare the current element (key) to its predecessor. If the key element is smaller than its predecessor, compare it to the elements before. Move the greater elements one position up to make space for the swapped element.

Example:

Consider an example array: {12, 11, 13, 5, 6}

Pass	Array
1	11 12 13 5 6
2	11 12 13 5 6
3	5 11 12 13 6
4	5 6 11 12 13

Finally, the array is completely sorted.

Sorting an Integer Array using Insertion Sort Algorithm in C