Insertion Sort in Ascending Order in C

1. Introduction

Insertion Sort is a comparison-based sorting algorithm that builds the final sorted array one item at a time. The fundamental concept behind Insertion Sort is to consider one element from the input elements in each iteration and move it to its correct position in the sorted array. This method is similar to the way we arrange our playing cards in our hands when playing a card game.

2. Program Overview

The program comprises the following components:

1. insertionSort: The main function that implements the Insertion Sort algorithm to sort in ascending order.

2. printArray: A utility function to display the contents of the array.

3. main: The primary function where the program begins its execution.

3. Code Program

#include <stdio.h>

// Implementation of insertionSort to sort in ascending order
void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];  // Take the current element
        j = i - 1;

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

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

// Main function to test the insertionSort function
int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr)/sizeof(arr[0]);
    insertionSort(arr, n);
    printf("Sorted array in ascending order: \n");
    printArray(arr, n);
    return 0;
}

Output:

Sorted array in ascending order:
5 6 11 12 13

4. Step By Step Explanation

The insertionSort function operates in the following step-by-step manner:

1. Start from the second element (consider the first element as sorted).

2. Pick the current element (referred to as key in the code) and compare it with the previous elements.

3. If the key element is smaller than the previous element, compare it with the elements before the previous element. Repeat this process until you reach a position where the previous element is smaller than the key or the start of the array. As we do this, we shift each of the compared elements up to make space for the key.

4. Once the correct position is found, the key is placed in its appropriate spot in the sorted subarray.

5. This process is repeated for each element in the array, resulting in a sorted array.

The beauty of Insertion Sort lies in its simplicity and its ability to adapt to different data scenarios. For a nearly sorted list, Insertion Sort can be highly efficient.

Related C Programs on Sorting Algorithms

1. Bubble Sort in Ascending Order in C
2. Bubble Sort in Descending Order in C
3. Selection Sort in Ascending Order in C
4. Selection Sort in Descending Order in C
5. Insertion Sort in Ascending Order in C
6. Insertion Sort in Descending Order in C
7. Merge Sort in Ascending Order in C
8. Merge Sort in Descending Order in C
9. Quick Sort in Ascending Order in C
10. Quick Sort in Descending Order in C
11. Heap Sort in Ascending Order in C
12. Heap Sort in Descending Order in C