C Program For Insertion Sort Using Function

In this article, you will learn how to implement the insertion sort algorithm in C programming language, specifically by encapsulating the sorting logic within a dedicated function for better modularity and reusability.

Problem Statement

Sorting is a fundamental operation in computer science, arranging elements of a list in a certain order. Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms like quicksort, heapsort, or merge sort. However, it offers advantages for small data sets or data that is already substantially sorted. The challenge is to implement this sorting logic as a reusable function in C.

Example

Consider an unsorted array: {12, 11, 13, 5, 6}. After applying insertion sort, the array will be sorted in ascending order: {5, 6, 11, 12, 13}.

Background & Knowledge Prerequisites

To understand this article, readers should be familiar with:

• C Programming Basics: Variables, data types, operators.
• Arrays: Declaring, initializing, and accessing elements.
• Loops: for and while loops for iteration.
• Functions: Defining and calling functions, passing arrays as arguments.

Use Cases or Case Studies

Insertion sort, despite its O(n^2) worst-case time complexity, has several practical applications:

• Small Datasets: For arrays with a small number of elements (e.g., less than 20-30), insertion sort can be faster than more complex algorithms due to its low constant factor.
• Nearly Sorted Data: If an array is mostly sorted and only a few elements are out of place, insertion sort performs very well, often with a near O(n) time complexity.
• Online Algorithms: It can sort a list as new elements are received. It's often used as part of more complex algorithms, such as hybrid sorting algorithms (e.g., Timsort and introsort), where it sorts small partitions.
• Linked Lists: It can be efficient for sorting linked lists where element swapping is easier than with arrays.

Solution Approaches

We will focus on implementing insertion sort using a function in C.

Implementing Insertion Sort with a Function

This approach encapsulates the core sorting logic within a function, making the code reusable and the main function cleaner.

Summary: The insertionSort function takes an array and its size, then iteratively inserts each element into its correct position within the already sorted part of the array.

// Insertion Sort using Function
#include <stdio.h> // Required for input/output operations

// Function to print an array
void printArray(int arr[], int size) {
    // Step 1: Iterate through the array from the first element to the last
    for (int i = 0; i < size; i++) {
        // Step 2: Print each element followed by a space
        printf("%d ", arr[i]);
    }
    // Step 3: Print a newline character to move to the next line
    printf("\\n");
}

// Function to perform insertion sort on an array
void insertionSort(int arr[], int size) {
    // Step 1: Outer loop to iterate from the second element to the last element
    // The first element (index 0) is considered already sorted
    for (int i = 1; i < size; i++) {
        // Step 2: Store the current element to be inserted in its correct position
        int key = arr[i];
        // Step 3: Initialize 'j' to the index of the element just before 'key'
        int j = i - 1;

        // Step 4: Inner loop to shift 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 with the next element
        }
        // Step 5: Place the 'key' (current element) in its correct sorted position
        arr[j + 1] = key;
    }
}

int main() {
    // Step 1: Declare and initialize an unsorted integer array
    int arr[] = {12, 11, 13, 5, 6};
    // Step 2: Calculate the size of the array
    int size = sizeof(arr) / sizeof(arr[0]);

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

    // Step 4: Call the insertionSort function to sort the array
    insertionSort(arr, size);

    // Step 5: Print the sorted array
    printf("Sorted array: ");
    printArray(arr, size);

    return 0; // Indicate successful execution
}

Run

Sample Output:

Original array: 12 11 13 5 6 
Sorted array: 5 6 11 12 13

Stepwise Explanation:

1. printArray Function:

• This helper function takes an integer array arr and its size as input.
• It iterates through the array and prints each element, followed by a space, then a newline character at the end. This helps visualize the array content.

1. insertionSort Function:

• Outer Loop (for (int i = 1; i < size; i++)): This loop iterates from the second element (i = 1) to the last element of the array. The element at arr[i] is considered the "key" to be inserted into the sorted subarray arr[0...i-1].
• int key = arr[i];: The value of the current element (arr[i]) is stored in key. This is crucial because elements might be shifted to the right, overwriting arr[i].
• int j = i - 1;: j is initialized to the index of the last element in the already sorted subarray (just before the key).
• Inner Loop (while (j >= 0 && arr[j] > key)): This loop compares key with elements in the sorted subarray (arr[0...j]) from right to left.
• If an element arr[j] is greater than key, it means key should be placed before arr[j]. So, arr[j] is shifted one position to the right (arr[j + 1] = arr[j]).
• j is decremented (j = j - 1) to move to the next element on the left in the sorted subarray.
• This shifting continues until j becomes negative (meaning key is the smallest element) or an element arr[j] is found that is less than or equal to key.
• arr[j + 1] = key;: Once the while loop terminates, j + 1 is the correct position for key in the sorted subarray. key is then placed at this position.

1. main Function:

• An unsorted integer array arr is declared and initialized.
• The size of the array is calculated using sizeof operators.
• The original array is printed using printArray.
• The insertionSort function is called, passing the array and its size, to sort the array in place.
• The sorted array is then printed using printArray.
• return 0; signifies successful program execution.

Conclusion

Implementing insertion sort using a function in C provides a clear, modular, and reusable solution for sorting arrays. While its performance is not optimal for very large datasets, its simplicity, low overhead, and efficiency with small or nearly sorted lists make it a valuable algorithm in specific scenarios. Encapsulating the logic in a function promotes good programming practices by separating concerns.

Summary

• Insertion Sort Basics: A simple sorting algorithm that builds a sorted array one element at a time.
• Function for Modularity: Using a void insertionSort(int arr[], int size) function enhances code reusability and readability.
• Algorithm Logic: Iterates through the array, taking each element (key) and inserting it into its correct position within the already sorted portion by shifting larger elements.
• Performance: Optimal for small arrays or nearly sorted data, but less efficient for large, randomly ordered datasets due to its O(n^2) worst-case time complexity.
• Helper Functions: A printArray function is useful for visualizing the array's state before and after sorting.