Implementation of Insertion Sort Algorithm in C

Insertion sort is an algorithm used to sort a list of items in ascending, descending or any other custom order. In this article, we’ll implement a basic version of insertion sort algorithm in C programming language which can sort a given list of numbers in ascending order. We’ll then explore several practical variations, including sorting in descending order and sorting custom structures.

Prerequisites:

Basic Insertion Sort Implementation

Let’s start with the standard iterative implementation of insertion sort. This version sorts an array in ascending order by repeatedly taking an element and inserting it into its correct position in the already sorted portion of the array.

#include <stdio.h>

void insertionSort(int arr[], int n) {
  // Handle empty or single-element arrays
  if (n <= 1) return;
  
  // Start from the second element
  for (int i = 1; i < n; i++) {
    int key = arr[i];  // Current element to be inserted
    int j = i - 1;     // Index of last element in sorted portion
    
    // Move elements greater than key ahead
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    
    // Place key in its correct position
    arr[j + 1] = key;
  }
}

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

int main() {
  // Test with a simple array
  int arr[] = {64, 34, 25, 12, 22, 11, 90};
  int n = sizeof(arr) / sizeof(arr[0]);
  
  printf("Original array: ");
  printArray(arr, n);
  
  insertionSort(arr, n);
  
  printf("Sorted array: ");
  printArray(arr, n);
  
  // Test with duplicates
  int arrWithDuplicates[] = {4, 3, 2, 4, 1, 2};
  int m = sizeof(arrWithDuplicates) / sizeof(arrWithDuplicates[0]);
  
  printf("\nOriginal array with duplicates: ");
  printArray(arrWithDuplicates, m);
  
  insertionSort(arrWithDuplicates, m);
  
  printf("Sorted array with duplicates: ");
  printArray(arrWithDuplicates, m);
  
  return 0;
}

Output:

Original array: 64 34 25 12 22 11 90 
Sorted array: 11 12 22 25 34 64 90 

Original array with duplicates: 4 3 2 4 1 2 
Sorted array with duplicates: 1 2 2 3 4 4

Sorting in Descending Order

Sometimes we need our data in reverse order, from largest to smallest. Here’s a modified version of insertion sort that arranges elements in descending order. The main difference is in the comparison operator - we use < instead of > to achieve descending order.

#include <stdio.h>

void insertionSortDesc(int arr[], int n) {
  if (n <= 1) return;
  
  for (int i = 1; i < n; i++) {
    int key = arr[i];
    int j = i - 1;
    
    // Notice the < operator instead of >
    while (j >= 0 && arr[j] < key) {
      arr[j + 1] = arr[j];
      j--;
    }
    
    arr[j + 1] = key;
  }
}

int main() {
  int arr[] = {64, 34, 25, 12, 22, 11, 90};
  int n = sizeof(arr) / sizeof(arr[0]);
  
  printf("Original array: ");
  printArray(arr, n);
  
  insertionSortDesc(arr, n);
  
  printf("Sorted array (descending): ");
  printArray(arr, n);
  
  return 0;
}

Output:

Original array: 64 34 25 12 22 11 90 
Sorted array (descending): 90 64 34 25 22 12 11

Sorting Structures

In real-world applications, we often need to sort arrays of structures based on specific fields. Here’s an example that demonstrates how to sort student records:

#include <stdio.h>
#include <string.h>

struct Student {
  char name[50];
  int age;
};

// Function to sort students by age
void sortStudentsByAge(struct Student arr[], int n) {
  if (n <= 1) return;
  for (int i = 1; i < n; i++) {
    struct Student key = arr[i];
    int j = i - 1;
    
    while (j >= 0 && arr[j].age > key.age) {
      arr[j + 1] = arr[j];
      j--;
    }
    
    arr[j + 1] = key;
  }
}

int main() {
  struct Student students[] = {
    {"Alice", 20},
    {"Bob", 19},
    {"Charlie", 21}
  };
  int n = sizeof(students) / sizeof(students[0]);
  
  printf("Original student array:\n");
  for (int i = 0; i < n; i++)
    printf("%s (%d)\n", students[i].name, students[i].age);
  
  sortStudentsByAge(students, n);
  
  printf("\nSorted student array (by age):\n");
  for (int i = 0; i < n; i++)
    printf("%s (%d)\n", students[i].name, students[i].age);
  
  return 0;
}

Output:

Original student array:
Alice (20)
Bob (19)
Charlie (21)

Sorted student array (by age):
Bob (19)
Alice (20)
Charlie (21)

What’s Next?

Now that you’ve learned how to implement insertion sort in C, you might want to explore: