C Program to Implement Insertion Sort

📘 Premium Read: Access my best content on Medium member-only articles — deep dives into Java, Spring Boot, Microservices, backend architecture, interview preparation, career advice, and industry-standard best practices.

🎓 Top 15 Udemy Courses (80-90% Discount): My Udemy Courses - Ramesh Fadatare — All my Udemy courses are real-time and project oriented courses.

▶️ Subscribe to My YouTube Channel (176K+ subscribers): Java Guides on YouTube

▶️ For AI, ChatGPT, Web, Tech, and Generative AI, subscribe to another channel: Ramesh Fadatare on YouTube

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.