Insertion Sort in C: Program to Sort Array Using Insertion Sort Algorithm

📚 In this tutorial, you will learn:

What is insertion sort and how it works
How to implement insertion sort in C
How insertion sort builds the final sorted array one element at a time
Step-by-step explanation of the program
Time and space complexity of insertion sort
Practice exercises to test your understanding

Introduction

In this tutorial, we will learn how to write a C program to sort an array using the insertion sort algorithm.

Insertion sort is a simple and intuitive sorting algorithm that builds the final sorted array one element at a time. It works by taking each element from the unsorted part and inserting it into its correct position in the sorted part of the array.

💡 Key Point: Insertion sort is similar to how you would sort playing cards in your hand. You pick up a card and insert it into the correct position among the already sorted cards.

Insertion sort is used in various scenarios, such as:

Small Datasets: Efficient for small or partially sorted arrays
Online Algorithms: Can sort data as it is received
Stable Sorting: Maintains relative order of equal elements
Adaptive: Performs better on nearly sorted data

Visual Example

Let's see how insertion sort sorts the array [64, 34, 25, 12, 22, 11, 90]:

Pass 1: Consider first element [64] as sorted

[64, 34, 25, 12, 22, 11, 90] → Insert 34 before 64 → [34, 64, 25, 12, 22, 11, 90]

Pass 2: Insert 25 into sorted part [34, 64]

[34, 64, 25, 12, 22, 11, 90] → Insert 25 before 34 → [25, 34, 64, 12, 22, 11, 90]

Pass 3: Insert 12 into sorted part [25, 34, 64]

[25, 34, 64, 12, 22, 11, 90] → Insert 12 at beginning → [12, 25, 34, 64, 22, 11, 90]

Pass 4: Insert 22 into sorted part [12, 25, 34, 64]

[12, 25, 34, 64, 22, 11, 90] → Insert 22 between 12 and 25 → [12, 22, 25, 34, 64, 11, 90]

Pass 5: Insert 11 into sorted part [12, 22, 25, 34, 64]

[12, 22, 25, 34, 64, 11, 90] → Insert 11 at beginning → [11, 12, 22, 25, 34, 64, 90]

Pass 6: Insert 90 into sorted part [11, 12, 22, 25, 34, 64]

[11, 12, 22, 25, 34, 64, 90] → 90 already at correct position → [11, 12, 22, 25, 34, 64, 90]

Final Sorted Array: [11, 12, 22, 25, 34, 64, 90]

C Program for Insertion Sort

#include <stdio.h>

int main() {
    int n, i, j, key;
    
    // Ask user for number of elements
    printf("Enter the number of elements: ");
    scanf("%d", &n);
    
    // Declare array
    int arr[n];
    
    // Read elements into the array
    printf("Enter %d elements:\n", n);
    for(i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    
    // Insertion Sort Algorithm
    for(i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;
        
        // Move elements greater than key to one position ahead
        while(j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
    
    // Display sorted array
    printf("\nSorted array in ascending order: ");
    for(i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    return 0;
}

Sample Output

Enter the number of elements: 7
Enter 7 elements:
64 34 25 12 22 11 90

Sorted array in ascending order: 11 12 22 25 34 64 90

Another Example:

Enter the number of elements: 5
Enter 5 elements:
5 1 4 2 8

Sorted array in ascending order: 1 2 4 5 8

Example with Negative Numbers:

Enter the number of elements: 6
Enter 6 elements:
-5 10 -2 8 0 -10

Sorted array in ascending order: -10 -5 -2 0 8 10

Program Explanation

Let's break down the code step by step:

Include Header File: #include <stdio.h> includes the standard input/output library.
Declare Variables:
- int n; — number of elements
- int i, j; — loop counters
- int key; — the element to be inserted
Get User Input: Reads the array elements from the user.
Insertion Sort:
- Outer Loop: for(i = 1; i < n; i++) — starts from the second element
- Store Key: key = arr[i]; — store the current element
- Inner Loop: while(j >= 0 && arr[j] > key) — shift elements greater than key
- Insert: arr[j + 1] = key; — place the key in its correct position
Display Result: Prints the sorted array.
Return: return 0; indicates successful program execution.

📝 Note: Insertion sort has a time complexity of O(n²) in the worst case and O(n) in the best case (when the array is already sorted).

Insertion Sort Algorithm

Step-by-step algorithm:

Start
Read the array elements
For i = 1 to n-1:
- Set key = arr[i]
- Set j = i - 1
- While j >= 0 and arr[j] > key:
  - Set arr[j + 1] = arr[j]
  - Set j = j - 1
- Set arr[j + 1] = key
Print the sorted array
End

Time and Space Complexity

Scenario	Time Complexity	Space Complexity
Best Case (Already Sorted)	O(n)	O(1)
Worst Case (Reverse Sorted)	O(n²)	O(1)
Average Case	O(n²)	O(1)

💡 Note: Insertion sort is adaptive and performs well on nearly sorted data. It is also stable, maintaining the relative order of equal elements.

💻 Practice Exercise

Challenge 1: Modify the insertion sort program to sort the array in descending order.

Challenge 2: Count the number of shifts performed during the insertion sort.

🔍 Click to Show Solution for Challenge 1

#include <stdio.h>

int main() {
    int n, i, j, key;
    
    printf("Enter the number of elements: ");
    scanf("%d", &n);
    
    int arr[n];
    
    printf("Enter %d elements:\n", n);
    for(i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    
    // Insertion Sort for Descending Order
    for(i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;
        
        // Move elements smaller than key to one position ahead
        while(j >= 0 && arr[j] < key) {  // Change > to < for descending
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
    
    printf("\nSorted array in descending order: ");
    for(i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    return 0;
}

Frequently Asked Questions

1. What is insertion sort in C?

Insertion sort is a simple sorting algorithm that builds the final sorted array one element at a time. It takes each element from the unsorted part and inserts it into its correct position in the sorted part.

2. What is the time complexity of insertion sort?

Insertion sort has a time complexity of O(n²) in the worst and average cases, and O(n) in the best case (when the array is already sorted).

3. Is insertion sort stable?

Yes, insertion sort is a stable sorting algorithm. It maintains the relative order of equal elements.

4. When is insertion sort preferred over other sorting algorithms?

Insertion sort is preferred for small datasets, partially sorted arrays, and when data is being received online (streaming data).

5. How is insertion sort different from selection sort?

Insertion sort builds the sorted array by inserting elements one at a time, while selection sort finds the minimum element and places it at the beginning in each pass. Insertion sort is adaptive and stable, while selection sort is not.

💡 Tip: Insertion sort is a great starting point for learning sorting algorithms. Once you understand it, you can move on to more efficient algorithms like Quick Sort or Merge Sort.

Previous Topic: -->> Selection Sort in C || Next topic: -->> Merge Sort in C

📚 Explore More Topics