C Program For Insertion Sort In Descending Order

This article will guide you through implementing the insertion sort algorithm in C, specifically tailored to sort an array of numbers in descending order. You will learn the core logic, see a practical code example, and understand its step-by-step execution.

Problem Statement

Sorting data is a fundamental operation in computer science. While ascending order sorting is common, there are many scenarios where arranging elements from largest to smallest (descending order) is required. The challenge is to adapt the classic insertion sort algorithm, known for its simplicity and efficiency with small datasets, to achieve this descending order sort.

Example

Consider an unsorted array: [5, 2, 8, 1, 9]

After applying descending insertion sort, the array should become: [9, 8, 5, 2, 1]

Background & Knowledge Prerequisites

To understand this article, you should be familiar with:

• C Programming Basics: Variables, data types, functions, and control structures (loops, conditionals).
• Arrays: How to declare, initialize, and access elements in C arrays.
• Basic Sorting Concepts: An introductory understanding of what sorting algorithms aim to achieve.

Use Cases or Case Studies

Sorting in descending order is useful in various practical applications:

• Leaderboards: Displaying game scores or competition results from highest to lowest.
• Top N Analysis: Identifying the highest-performing items, sales, or employees in a dataset.
• Prioritization Queues: Arranging tasks or events based on urgency, with the highest priority first.
• Inventory Management: Listing products by their current stock level, starting with the most abundant.
• Financial Reports: Presenting revenue or profit figures from the largest to the smallest contributor.

Solution Approaches

Insertion sort works by building a final sorted array (or list) one item at a time. It iterates through the input elements and at each iteration, removes one element from the input data and inserts it into the correct position in the already sorted list.

Descending Insertion Sort Algorithm

This approach adapts the standard insertion sort by changing the comparison logic to place larger elements before smaller ones.

One-line summary: Iterate through the array, taking each element and inserting it into its correct descending position within the already sorted part of the array.

// Insertion Sort in Descending Order
#include <stdio.h>

// Function to perform insertion sort in descending order
void insertionSortDescending(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i]; // Current element to be inserted
        j = i - 1;    // Index of the last element in the sorted subarray

        // Move elements of arr[0..i-1], that are smaller than key,
        // to one position ahead of their current position.
        // This creates space for 'key' at the correct descending position.
        while (j >= 0 && arr[j] < key) { // Changed from arr[j] > key for ascending
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key; // Place key at its correct position
    }
}

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

int main() {
    // Step 1: Initialize an unsorted array
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: ");
    printArray(arr, n);

    // Step 2: Call the insertion sort function for descending order
    insertionSortDescending(arr, n);

    printf("Sorted array (descending): ");
    printArray(arr, n);

    return 0;
}

Run

Sample Output:

Original array: 12 11 13 5 6 
Sorted array (descending): 13 12 11 6 5

Stepwise Explanation:

1. Outer Loop (for (i = 1; i < n; i++)): This loop iterates from the second element (i = 1) up to the last element of the array. Each element arr[i] is considered as the key to be inserted into its correct position in the already sorted subarray arr[0...i-1].
2. Store key: key = arr[i]; saves the current element that needs to be positioned.
3. Inner Loop Initialization (j = i - 1;): j points to the last element of the sorted subarray. We will compare key with elements from arr[j] backwards.
4. Comparison and Shifting (while (j >= 0 && arr[j] < key)):

• This is the core change for descending order. Instead of arr[j] > key (for ascending), we use arr[j] < key.
• If arr[j] (an element in the sorted part) is smaller than key, it means key should come before arr[j] in descending order.
• So, arr[j] is shifted one position to the right (arr[j + 1] = arr[j]), making space for key.
• j is decremented (j = j - 1;) to move to the previous element in the sorted subarray and continue the comparison.

1. Insert key (arr[j + 1] = key;): Once the while loop terminates, it means we've found the correct position for key (either j went below 0, or arr[j] is no longer smaller than key). The key is then placed at arr[j + 1].

Conclusion

Implementing insertion sort for descending order involves a minor but crucial change in the comparison logic within the algorithm. By adjusting the condition from checking arr[j] > key to arr[j] < key, we ensure that larger elements are prioritized and shifted to the left, resulting in a correctly sorted array from largest to smallest. This demonstrates the adaptability of fundamental sorting algorithms to various requirements.

Summary

• Insertion sort builds a sorted array one element at a time.
• To sort in descending order, the key modification is in the comparison condition: arr[j] < key.
• If an element in the sorted subarray (arr[j]) is smaller than the key element, arr[j] is shifted to the right.
• This process continues until the correct position for key is found, ensuring elements are placed in decreasing order.
• Insertion sort is simple to implement and efficient for small datasets or nearly sorted arrays.