C Program Of Simple Insertion Sort Implementation Using Array In Ascending Order

Insertion sort is a straightforward sorting algorithm suitable for small datasets or nearly sorted arrays. In this article, you will learn how to implement a simple insertion sort using an array in C to sort elements in ascending order.

Problem Statement

Efficiently organizing data is fundamental in computer science. The problem addressed here is how to arrange a collection of elements, specifically integers in an array, into a specific order (ascending) using an intuitive sorting algorithm. This allows for easier searching, merging, and analysis of data.

Example

Consider an unsorted array of integers. After applying insertion sort, the elements will be rearranged into ascending order.

Input Array: [12, 11, 13, 5, 6] Output Array: [5, 6, 11, 12, 13]

Background & Knowledge Prerequisites

To understand the C implementation of insertion sort, readers should have a basic understanding of:

• C Language Fundamentals: Basic syntax, variable declaration, data types.
• Arrays: How to declare, initialize, and access elements in a one-dimensional array.
• Loops: for and while loops for iteration.
• Conditional Statements: if statements for comparisons.

Use Cases or Case Studies

Insertion sort, despite its O(n^2) worst-case time complexity, finds practical application in several scenarios:

• Small Datasets: It performs well for small arrays where its simplicity and low overhead outweigh its quadratic complexity.
• Nearly Sorted Data: If an array is already mostly sorted, insertion sort can be very efficient, approaching O(n) performance.
• Online Algorithms: When data arrives sequentially and needs to be kept sorted, insertion sort can efficiently insert new elements into an already sorted list.
• Teaching/Learning Sorting Algorithms: Its intuitive nature makes it an excellent algorithm for introductory computer science courses.
• Hybrid Sorting Algorithms: It is often used as a sub-routine in more advanced sorting algorithms like Introsort, which switch to insertion sort for smaller partitions.

Solution Approaches

Simple Insertion Sort Algorithm

This approach sorts an array by repeatedly picking an element from the unsorted part and inserting it into its correct position within the already sorted part of the array.

// Simple Insertion Sort
#include <stdio.h>

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

// Function to perform insertion sort
void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i]; // Store the current element to be inserted
        j = i - 1;   // Start comparing with the element just before 'key'

        // 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]; // Shift element to the right
            j = j - 1;           // Move to the left to compare next element
        }
        arr[j + 1] = key; // Place key in its correct position
    }
}

int main() {
    // Step 1: Define an array
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]); // Calculate size of the array

    // Step 2: Print the original array
    printf("Original array: ");
    printArray(arr, n);

    // Step 3: Perform insertion sort
    insertionSort(arr, n);

    // Step 4: Print the sorted array
    printf("Sorted array (ascending): ");
    printArray(arr, n);

    return 0;
}

Run

Sample Output:

Original array: 12 11 13 5 6 
Sorted array (ascending): 5 6 11 12 13

Stepwise Explanation:

1. Outer Loop (for (i = 1; i < n; i++)): This loop iterates from the second element (i = 1) up to the last element of the array. The first element (arr[0]) is considered to be a sorted sub-array of size 1.
2. Select Key (key = arr[i]): In each iteration, the current element arr[i] is chosen as the key. This key is the element we want to insert into the correct position within the already sorted sub-array arr[0...i-1].
3. Inner Loop (while (j >= 0 && arr[j] > key)):

• j = i - 1: A pointer j is initialized to point to the last element of the sorted sub-array.
• This loop compares key with elements in the sorted sub-array, moving from right to left (j >= 0).
• If an element arr[j] in the sorted sub-array is greater than the key, it means key should be placed before arr[j].
• arr[j + 1] = arr[j]: To make space for key, arr[j] is shifted one position to the right.
• j = j - 1: The j pointer moves one step to the left to compare key with the next element in the sorted sub-array.

1. Insert Key (arr[j + 1] = key): Once the while loop terminates (either j becomes negative, meaning key is the smallest element, or arr[j] is less than or equal to key), the key is inserted at the position j + 1. This is its correct sorted position.

Conclusion

Insertion sort offers a simple and intuitive way to sort arrays, particularly effective for smaller datasets or data that is already nearly sorted. Its in-place nature and minimal auxiliary space requirements make it a valuable algorithm to understand. While its O(n^2) worst-case time complexity limits its use for very large, randomly ordered arrays, its efficiency in specific contexts ensures its continued relevance.

Summary

• Insertion sort is an in-place comparison-based sorting algorithm.
• It builds the final sorted array one item at a time.
• The algorithm iterates through the array, taking each element and inserting it into its correct position within the already sorted portion of the array.
• It is efficient for small datasets and nearly sorted arrays.
• Time complexity is O(n^2) in the worst and average cases, and O(n) in the best case (when the array is already sorted).
• Space complexity is O(1) as it sorts in-place.