Insertion Sort in Descending Order in C

1. Introduction

Insertion Sort, a simple and intuitive comparison-based sorting algorithm, works by building the final sorted array one item at a time. It is very similar to how we sort playing cards in our hands. When sorting in descending order, the algorithm compares each element and places it in its correct position among the already sorted elements, ensuring that the highest values appear first.

2. Program Overview

The structure of the program is:

1. insertionSortDesc: The primary function that implements the Insertion Sort algorithm for descending order.

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

3. main: The main function where the program starts execution.

3. Code Program

#include <stdio.h>

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

        /* Move elements of arr[0..i-1] that are smaller 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;  // Position the key at its correct position
    }
}

// Utility function to display the array's content
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 insertionSortDesc function
int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr)/sizeof(arr[0]);
    insertionSortDesc(arr, n);
    printf("Sorted array in descending order: \n");
    printArray(arr, n);
    return 0;
}

Output:

Sorted array in descending order:
13 12 11 6 5

4. Step By Step Explanation

The insertionSortDesc function works as follows:

1. Beginning with the second element (assuming the first element is sorted), we pick each element in the array.

2. This element, referred to as key in the code, is compared with the elements before it.

3. If the key is larger than the preceding element, it is then compared with the elements before that element. This continues until the start of the array or until we find an element larger than the key.

4. During this comparison process, we shift each of the compared elements down to create space for the key.

5. Once the right position for the key has been determined, it's placed in its appropriate spot within the sorted section.

6. This process is repeated for all the elements in the array, ensuring that the array gets sorted in descending order.

In scenarios where the list is nearly sorted but in reverse order, Insertion Sort can be particularly efficient, as it only needs to reorder elements as necessary.

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