C++ Program For Insertion Sort In Descending Order

In this article, you will learn how to implement the insertion sort algorithm in C++ to arrange elements in descending order. This process involves a slight modification to the standard ascending insertion sort logic, allowing you to sort data from largest to smallest.

Problem Statement

Sorting data is a fundamental operation in computer science. While ascending order (smallest to largest) is common, there are many scenarios where descending order (largest to smallest) is required. For instance, displaying a leaderboard, ranking products by sales, or prioritizing tasks based on urgency often demands a descending sort. The challenge is to adapt the classic insertion sort algorithm, known for its simplicity and efficiency on nearly sorted data, to achieve this specific ordering.

Example

Consider an unsorted array: [5, 2, 8, 1, 9]. Applying insertion sort in descending order would yield: [9, 8, 5, 2, 1].

Background & Knowledge Prerequisites

To understand this article, you should have a basic understanding of:

• C++ Fundamentals: Variables, data types, basic input/output.
• Arrays: How to declare, initialize, and access elements in C++.
• Loops: for and while loops for iteration.
• Functions: How to define and call functions in C++.

Use Cases or Case Studies

Here are a few practical applications where descending order sorting is beneficial:

• Leaderboards: Displaying game scores or competition results from highest to lowest.
• E-commerce Product Listings: Showing products by "highest rated" or "most expensive" first.
• Recent Activity Feeds: Arranging news articles or social media posts with the newest appearing at the top.
• Priority Queues: Organizing tasks or events based on their urgency or importance, with the highest priority items processed first.
• Financial Reports: Listing sales figures, profits, or stock prices in decreasing order to highlight top performers.

Solution Approaches

We will focus on the direct modification of the standard insertion sort algorithm to achieve descending order.

Approach 1: Modified Insertion Sort for Descending Order

This approach adapts the core comparison logic within the standard insertion sort. Instead of shifting elements that are *greater* than the current key, we shift elements that are *smaller* than the current key to make space for it in the correct descending position.

One-line summary: Iterate through the array, taking each element and inserting it into its correct position within the already sorted portion, ensuring larger elements precede smaller ones.

Code example:

// Insertion Sort Descending
#include <iostream> // Required for input/output operations
#include <vector>   // Required for using std::vector

// Function to print the elements of a vector
void printArray(const std::vector<int>& arr) {
    for (int i = 0; i < arr.size(); ++i) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
}

// Function to perform insertion sort in descending order
void insertionSortDescending(std::vector<int>& arr) {
    int n = arr.size(); // Get the number of elements in the array

    // Iterate from the second element to the end of the array
    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 subarray

        // 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]; // Shift element to the right
            j = j - 1;           // Move to the previous element in the sorted subarray
        }
        arr[j + 1] = key; // Place the key in its correct descending position
    }
}

int main() {
    // Step 1: Initialize an unsorted vector
    std::vector<int> numbers = {5, 2, 8, 1, 9, 3, 7};

    // Step 2: Print the original array
    std::cout << "Original array: ";
    printArray(numbers);

    // Step 3: Perform insertion sort in descending order
    insertionSortDescending(numbers);

    // Step 4: Print the sorted array
    std::cout << "Sorted array (descending): ";
    printArray(numbers);

    return 0; // Indicate successful execution
}

Run

Sample output:

Original array: 5 2 8 1 9 3 7 
Sorted array (descending): 9 8 7 5 3 2 1

Stepwise explanation:

1. insertionSortDescending(std::vector& arr) function:

• It takes a std::vector by reference, allowing the function to modify the original array.
• n stores the total number of elements.

1. Outer Loop (for (int i = 1; i < n; ++i)):

• This loop iterates from the second element (i = 1) up to the last element of the array. The first element (arr[0]) is considered trivially sorted.
• In each iteration, arr[i] is the "key" element that needs to be inserted into its correct position within the already sorted subarray arr[0...i-1].

1. Store key and Initialize j:

• int key = arr[i]; saves the value of the current element to be placed.
• int j = i - 1; initializes j to point to the last element of the sorted subarray.

1. Inner Loop (while (j >= 0 && arr[j] < key)):

• This while loop is the core of the descending sort modification.
• It continues as long as j is a valid index (not less than 0) AND the element at arr[j] is *smaller* than key.
• Crucial Change: For descending order, if arr[j] is *smaller* than key, it means arr[j] is in the wrong place relative to key (it should come *after* key). So, we need to shift arr[j] to the right to make space for key.

1. Shifting Elements:

• arr[j + 1] = arr[j]; moves the element arr[j] one position to the right.
• j = j - 1; decrements j to compare key with the next element to its left in the sorted subarray.

1. Place key:

• Once the while loop finishes (either j becomes negative or arr[j] is no longer smaller than key), it means the correct position for key has been found.
• arr[j + 1] = key; places the key element into this newly created space.

Conclusion

Insertion sort, with a minor adjustment to its comparison logic, effectively sorts an array in descending order. By shifting elements *smaller* than the current key, we ensure that larger values propagate to the left, creating a sorted sequence from highest to lowest. This method remains straightforward and efficient, especially for datasets that are already mostly sorted.

Summary

• Insertion sort works by iteratively building a sorted subarray from left to right.
• For descending order, the key modification is in the comparison: elements *smaller* than the current key are shifted to the right.
• The algorithm is intuitive and easy to implement.
• It is particularly efficient for small datasets or arrays that are nearly sorted.