C++ Program To Sort String In Descending Order

String manipulation is a fundamental task in programming, and sorting characters within a string is a common requirement. When data needs to be presented or processed from largest to smallest, descending order sorting becomes essential.

In this article, you will learn various C++ programming approaches to sort a string in descending order, enhancing your ability to handle string data efficiently.

Problem Statement

The core problem is to rearrange the characters of a given string such that they appear in descending alphabetical or ASCII order. This means characters with higher ASCII values (like 'z' before 'a', or '9' before '0') should come first. For instance, if the input string is "hello", the desired output would be "ollhe".

Example

Consider the input string "programming". When sorted in descending order, the characters would be arranged as: "rrponmmig".

Background & Knowledge Prerequisites

To effectively understand the solutions presented, a basic grasp of the following C++ concepts is helpful:

• C++ Syntax Basics: Fundamental understanding of variables, loops, and conditional statements.
• std::string: Familiarity with how std::string objects are declared and manipulated.
• Standard Template Library (STL): An understanding of what the STL is, particularly algorithms like std::sort and iterators (begin(), end(), rbegin(), rend()).
• Comparators: Knowledge of how to provide custom comparison logic to sorting algorithms.

Use Cases or Case Studies

Sorting strings in descending order can be valuable in several practical scenarios:

• Lexicographical Ordering for Search Results: Displaying search results or lists where items with higher character values (e.g., product names, codes) should appear at the top, such as "Z-A" sorting in e-commerce.
• Data Preprocessing for Analysis: When standardizing data for analysis, a consistent descending order might be required for specific comparison algorithms or indexing structures.
• Generating Permutations or Anagrams: In computational linguistics or puzzle-solving, generating specific permutations of characters where a reverse alphabetical order is part of the pattern.
• Password Complexity Analysis: While not a direct sorting use, understanding character distribution after sorting (including reverse sorting) can contribute to analyzing the entropy or patterns in passwords.
• Ranking Systems: In some custom ranking or scoring systems, where string identifiers need to be ordered from highest to lowest based on their character values.

Solution Approaches

Here are three common approaches to sort a string in descending order using C++.

Approach 1: Using std::sort with Reverse Iterators (std::rbegin(), std::rend())

This approach leverages the std::sort algorithm from the C++ Standard Library with reverse iterators, which allows sorting elements from the end of the string towards the beginning.

// Sort String Descending with Reverse Iterators
#include <iostream>
#include <string>    // Required for std::string
#include <algorithm> // Required for std::sort
using namespace std;

int main() {
    // Step 1: Initialize the string
    string myString = "programming";
    cout << "Original string: " << myString << endl;

    // Step 2: Sort the string in descending order using reverse iterators
    // std::rbegin() gives a reverse iterator to the last element.
    // std::rend() gives a reverse iterator to the element before the first.
    // std::sort sorts the range in ascending order of the reverse traversal,
    // which effectively sorts the original string in descending order.
    std::sort(myString.rbegin(), myString.rend());

    // Step 3: Print the sorted string
    cout << "Sorted string (descending): " << myString << endl;

    return 0;
}

Run

Sample Output:

Original string: programming
Sorted string (descending): rrponmmig

Stepwise Explanation:

1. A std::string named myString is initialized with characters.
2. std::sort is called, but instead of begin() and end(), it uses myString.rbegin() and myString.rend().
3. rbegin() returns a reverse iterator pointing to the last character of the string, and rend() returns a reverse iterator pointing to the theoretical element before the first character.
4. When std::sort operates on these reverse iterators, it sorts the elements in ascending order *along the reverse path*. This effectively results in the original string being sorted in descending order from its begin() to end().

Approach 2: Using std::sort with a Custom Comparator (std::greater)

This method directly tells std::sort to use a "greater than" comparison for sorting, thus arranging characters in descending order.

// Sort String Descending with std::greater
#include <iostream>
#include <string>    // Required for std::string
#include <algorithm> // Required for std::sort
#include <functional> // Required for std::greater
using namespace std;

int main() {
    // Step 1: Initialize the string
    string myString = "hello_world";
    cout << "Original string: " << myString << endl;

    // Step 2: Sort the string in descending order using std::greater<char>()
    // std::greater<char>() is a function object that defines a 'greater than' comparison.
    // std::sort uses this comparator to place larger characters before smaller ones.
    std::sort(myString.begin(), myString.end(), std::greater<char>());

    // Step 3: Print the sorted string
    cout << "Sorted string (descending): " << myString << endl;

    return 0;
}

Run

Sample Output:

Original string: hello_world
Sorted string (descending): worlld_eh

Stepwise Explanation:

1. A std::string named myString is initialized.
2. std::sort is called with myString.begin(), myString.end(), and a third argument: std::greater().
3. std::greater() is a predefined function object (a "functor") from the header that performs a comparison: a > b.
4. By providing this custom comparator, std::sort arranges the elements such that if myString[i] is "greater than" myString[j], myString[i] comes before myString[j], thus achieving descending order.

Approach 3: Manual Sorting (Bubble Sort)

For educational purposes or scenarios where std::sort is unavailable or disallowed, a manual sorting algorithm like Bubble Sort can be implemented. While generally less efficient than std::sort for larger inputs, it demonstrates the underlying logic.

// Sort String Descending with Bubble Sort
#include <iostream>
#include <string>    // Required for std::string
#include <algorithm> // Required for std::swap
using namespace std;

int main() {
    // Step 1: Initialize the string
    string myString = "coding";
    cout << "Original string: " << myString << endl;

    // Step 2: Implement Bubble Sort for descending order
    int n = myString.length();
    // Outer loop for passes
    for (int i = 0; i < n - 1; ++i) {
        // Inner loop for comparisons and swaps
        for (int j = 0; j < n - i - 1; ++j) {
            // Compare adjacent characters.
            // If the current character is less than the next, swap them.
            // This 'bubbles up' larger characters towards the beginning.
            if (myString[j] < myString[j+1]) {
                std::swap(myString[j], myString[j+1]);
            }
        }
    }

    // Step 3: Print the sorted string
    cout << "Sorted string (descending): " << myString << endl;

    return 0;
}

Run

Sample Output:

Original string: coding
Sorted string (descending): onigdc

Stepwise Explanation:

1. A std::string named myString is initialized.
2. The code uses two nested for loops, characteristic of Bubble Sort.
3. The outer loop controls the number of passes through the string.
4. The inner loop compares adjacent characters (myString[j] and myString[j+1]).
5. If myString[j] is found to be *less than* myString[j+1], their positions are swapped using std::swap. This ensures that the larger character moves to the left.
6. After each pass of the outer loop, the largest unsorted character is correctly placed. After all passes, the string is fully sorted in descending order.

Conclusion

C++ offers flexible and efficient ways to sort strings in descending order, primarily through the powerful std::sort algorithm. Whether using reverse iterators or explicitly defining a "greater than" comparison with std::greater(), std::sort provides an optimized and readable solution. While manual sorting algorithms like Bubble Sort are valuable for understanding the underlying mechanics, std::sort remains the most idiomatic and performance-friendly choice for practical applications.

Summary

• std::sort with rbegin() and rend(): Sorts a string in descending order by applying an ascending sort on its reverse view. It's concise and efficient.
• std::sort with std::greater(): Directly sorts a string in descending order by providing a custom comparator that defines "greater than" as the sorting criterion. This is also efficient and explicit.
• Manual Sorting (e.g., Bubble Sort): Involves implementing the sorting logic manually through loops and comparisons. While educational, it is generally less efficient than std::sort for larger inputs.
• For most C++ development, leveraging the STL's std::sort with either reverse iterators or std::greater() is the recommended approach due to its performance, robustness, and readability.