C Program For Insertion Sort Without Using Function

Sorting is a fundamental operation in computer science, crucial for organizing data efficiently. Among various sorting algorithms, insertion sort stands out for its simplicity and efficiency on small or nearly sorted datasets.

In this article, you will learn how to implement the insertion sort algorithm in C directly within the main function, without relying on any additional user-defined functions.

Problem Statement

The problem is to arrange a given array of elements in a specific order, typically ascending or descending. For instance, transforming an unsorted list of numbers like [5, 2, 4, 6, 1, 3] into a sorted sequence [1, 2, 3, 4, 5, 6]. Efficiently sorting data is vital for various applications, from database management to search algorithms, as it significantly improves data retrieval and processing speeds.

Example

Consider an array [12, 11, 13, 5, 6]. Insertion sort works by iteratively building a sorted sub-array.

• Initial: [12, 11, 13, 5, 6] (Sorted part: [12])
• Step 1 (11): [11, 12, 13, 5, 6] (11 is smaller than 12, so it moves before it. Sorted part: [11, 12])
• Step 2 (13): [11, 12, 13, 5, 6] (13 is greater than 12, stays. Sorted part: [11, 12, 13])
• Step 3 (5): [5, 11, 12, 13, 6] (5 is smaller than 13, 12, 11, moves to the beginning. Sorted part: [5, 11, 12, 13])
• Step 4 (6): [5, 6, 11, 12, 13] (6 is smaller than 13, 12, 11, but greater than 5, so it inserts after 5. Sorted part: [5, 6, 11, 12, 13])

The final sorted array is [5, 6, 11, 12, 13].

Background & Knowledge Prerequisites

To understand and implement insertion sort in C, readers should have a basic understanding of:

• C Programming Basics: Fundamental syntax, data types, variable declaration.
• Arrays: How to declare, initialize, and access elements in an array.
• Loops: for and while loops for iteration over array elements.
• Conditional Statements: if statements for comparisons.

There are no special libraries required beyond the standard input/output functions.

Use Cases or Case Studies

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

• Small Datasets: It is efficient for sorting small numbers of elements, often outperforming more complex algorithms due to its low overhead.
• Nearly Sorted Data: When an array is already partially sorted, insertion sort performs exceptionally well, as it only needs to shift elements a short distance. Its complexity approaches O(n) in this scenario.
• Online Algorithms: It can sort a list as it receives new elements. This is useful in scenarios where data arrives sequentially and needs to be kept sorted incrementally.
• Hybrid Sorting Algorithms: Many advanced sorting algorithms, like Timsort and Introsort, use insertion sort for sorting small sub-arrays within their larger sorting process.
• Linked Lists: Insertion sort is also effective for sorting linked lists, where inserting an element involves simply changing pointers, which is more efficient than array shifts.

Solution Approaches

For the requirement of implementing insertion sort *without using functions*, the primary approach involves a direct, iterative implementation within the main function.

Direct Iterative Implementation

This approach involves embedding the entire sorting logic directly within the main function using nested loops.

• Summary: The algorithm iterates through the array, taking one element at a time and inserting it into its correct position within the already sorted part of the array.

// Insertion Sort without Functions
#include <stdio.h> // Required for input/output operations

int main() {
    // Step 1: Declare and initialize the array
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]); // Calculate the number of elements

    printf("Original array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\\n");

    // Step 2: Implement the Insertion Sort logic
    // Start from the second element (index 1) as the first element
    // is considered already sorted in a sub-array of size 1.
    for (int i = 1; i < n; i++) {
        int key = arr[i]; // Store the current element to be inserted
        int j = i - 1;    // Initialize j to the last element of the sorted sub-array

        // 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 in the sorted sub-array
        }
        arr[j + 1] = key; // Place the key in its correct position
    }

    // Step 3: Print the sorted array
    printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\\n");

    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. Initialization: An integer array arr is declared and initialized with unsorted values. The n variable stores the total number of elements in the array.
2. Outer Loop (for i = 1 to n-1): This loop iterates from the second element (arr[1]) up to the last element. Each i represents the element that needs to be inserted into its correct position within the previously sorted sub-array (arr[0...i-1]).
3. key Variable: Inside the loop, key = arr[i] temporarily stores the current element that is to be positioned. This is important because elements to its left might be shifted, overwriting arr[i].
4. Inner Loop (while j >= 0 && arr[j] > key):

• j is initialized to i - 1, pointing to the last element of the sorted sub-array.
• This while loop compares key with elements in the sorted sub-array (arr[0...j]) from right to left.
• If an element arr[j] is greater than key, it means arr[j] is not in its correct place relative to key. 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 sub-array, continuing the comparison.

1. Placement of key: Once the while loop terminates (either j becomes negative, meaning key is the smallest so far, or arr[j] is less than or equal to key), the key is placed at arr[j + 1]. This is the first position where key is greater than or equal to arr[j] (or j went out of bounds).
2. Printing: After the outer loop completes, the array is fully sorted, and its elements are printed to the console.

Conclusion

Implementing insertion sort directly within the main function in C provides a clear understanding of its mechanics without the abstraction of additional functions. This direct approach highlights how the algorithm iteratively builds a sorted sequence by taking elements one by one and inserting them into their correct positions within an ever-growing sorted sub-array. While simple and efficient for small or nearly sorted lists, its O(n^2) worst-case performance makes it less suitable for very large, randomly ordered datasets.

Summary

• Insertion sort works by building a sorted array one element at a time.
• It iterates through the array, taking each element and inserting it into its correct place in the already sorted portion.
• The implementation in C requires nested loops: an outer loop to pick elements and an inner loop to shift elements for insertion.
• It is efficient for small datasets, nearly sorted data, and online sorting scenarios.
• The C code includes array declaration, sorting logic using for and while loops, and printing the results, all within the main function.