Insertion Sort In C

The algorithm then proceeds to compare every unsorted item to the elements within the sorted section, starting from the end, and shifts larger items one place to the right until the unsorted item is positioned correctly.

Once the appropriate position is identified, the unordered item is inserted into the ordered section at that specific placement.

This process is iterated until all elements from the unsorted section are added into the sorted section, leading to a completely organized array.

Here is the insertion sort pseudocode:

for i from 1 to n-1
    key = arr[i]
    j = i - 1
    while j >= 0 and arr[j] > key
        arr[j+1] = arr[j]
        j = j - 1
    arr[j+1] = key

In this pseudocode, n denotes the quantity of elements in the array, arr denotes the array intended for sorting, i and j serve as iteration variables, and key signifies the element to be added into the sorted portion of the array.

Usage:

Insertion sort proves to be beneficial in sorting small arrays and demonstrates acceptable efficiency especially with partially pre-sorted input arrays. It is commonly employed as a foundational component in more sophisticated sorting algorithms like merge sort and quicksort.

Here's an illustration of insertion sort in C:

#include <stdio.h>

void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;

        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

int main() {
    int arr[] = { 12, 11, 13, 5, 6 };
    int n = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, n);
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

Output:

5 6 11 12 13

This code presents the insertionSort function, designed to accept an array of integers named arr and its size denoted by n as arguments. The function utilizes a for loop to iterate over each element in the array, starting from the second element as the initial element is already considered sorted.

The function saves the value of every element in a variable named key and assigns a variable j to represent the index of the element before it. Subsequently, the code utilizes a while loop to compare the key with each preceding element until determining the suitable position for the key.

Each item larger than the key is shifted to the right by one position, while the index j is decremented until it reaches the accurate location. Then, the key is added to the correct position by assigning it to arr[j + 1].

Finally, the primary function utilizes a sample array along with its size to execute the insertionSort algorithm, resulting in the sorted array.

Advantages:

• ✅ Easy implementation: Because the approach is simple to build and understand, it is a great option for teaching basic sorting concepts.
• ✅ Because it sorts the array in place, insertion sort does not require any additional memory space.
• ✅ Insertion sort is an adaptive sorting algorithm that works best with partially sorted input arrays.
• ✅ Stable sorting means that the method keeps equal elements in the input array in the same relative order.

Disadvantages:

• ✅ Slow for large arrays: With an average time complexity of O(n2), the algorithm is slow for large arrays.
• ✅ Insertion sort is inefficient for random input arrays because it involves a large number of comparisons and shifts.
• ✅ The algorithm is not suited for parallelization since each iteration is dependent on the outcome of the preceding iteration.

Conclusion:

Insertion sort offers a simple and effective method for sorting small or partially ordered arrays. While it may not be the best choice for large arrays or random data, it can serve as a building block for more sophisticated sorting algorithms. In summary, insertion sort is a reliable option for sorting small or partially ordered arrays efficiently while keeping memory usage low.