C Program To Sort String In Descending Order

When working with character data in C, sorting strings is a common task, often required for data processing, lexicographical comparisons, or display purposes. In this article, you will learn how to sort the characters within a given string in descending order using C programming.

Problem Statement

The challenge is to rearrange the characters of an input string such that they appear in reverse alphabetical order (descending order). This means that characters with higher ASCII values (like 'z' before 'a', or '9' before '0') should come first. This operation is fundamental for tasks requiring specific character sequence arrangements.

Example

Consider the input string: "programming"

After sorting its characters in descending order, the expected output is: "rrpomniigg"

Background & Knowledge Prerequisites

To effectively understand and implement string sorting in C, familiarity with the following concepts is beneficial:

• C Arrays: Strings in C are essentially character arrays.
• Pointers: Understanding how pointers interact with arrays (especially char*).
• Loops: for and while loops are crucial for iterating through strings.
• Conditional Statements: if statements are used for character comparisons during sorting.
• Standard I/O: Using stdio.h for input (scanf, gets, fgets) and output (printf).
• String Manipulation Functions: Basic functions from string.h like strlen() to determine string length.
• Basic Sorting Algorithms: A conceptual understanding of algorithms like Bubble Sort or Selection Sort is helpful, as string sorting often adapts these.

Use Cases or Case Studies

Sorting strings in descending order can be useful in several scenarios:

• Lexicographical Ordering: In custom dictionaries or data structures where elements need to be ordered from Z-A.
• Data Analysis: When analyzing frequency distributions of characters, sorting can help group similar characters for easier counting.
• Password/Key Generation: Generating complex keys or passwords that follow a specific character order.
• Text Processing: Preparing text for specific transformations or encryption algorithms that rely on character order.
• Unique ID Generation: Creating unique identifiers where a descending sort of constituent characters is part of the generation logic.

Solution Approaches

Here, we will explore two common manual sorting algorithms adapted for sorting characters within a string.

Approach 1: Using Bubble Sort

Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. For descending order, we swap if the current element is smaller than the next.

• One-line summary: Iteratively compares and swaps adjacent characters to move larger characters towards the beginning of the string.

// Sort String Descending (Bubble Sort)
#include <stdio.h>
#include <string.h> // Required for strlen()

int main() {
    char str[] = "programming";
    int length = strlen(str);
    int i, j;
    char temp;

    printf("Original string: %s\\n", str);

    // Step 1: Outer loop for passes through the string
    for (i = 0; i < length - 1; i++) {
        // Step 2: Inner loop for comparisons and swaps
        for (j = 0; j < length - 1 - i; j++) {
            // Step 3: Compare adjacent characters
            // For descending order, if current is smaller than next, swap
            if (str[j] < str[j+1]) {
                // Step 4: Swap characters
                temp = str[j];
                str[j] = str[j+1];
                str[j+1] = temp;
            }
        }
    }

    // Step 5: Print the sorted string
    printf("Sorted string (descending): %s\\n", str);

    return 0;
}

Run

Sample Output:

Original string: programming
Sorted string (descending): rrpomniigg

Stepwise Explanation:

1. Initialize: We define a character array str and calculate its length using strlen().
2. Outer Loop: The for (i = 0; i < length - 1; i++) loop controls the number of passes. In each pass, at least one element "bubbles" to its correct position.
3. Inner Loop: The for (j = 0; j < length - 1 - i; j++) loop iterates through adjacent elements. The length - 1 - i part optimizes the loop, as the last i elements are already sorted.
4. Comparison and Swap: Inside the inner loop, if (str[j] < str[j+1]) checks if the current character str[j] is smaller than the next str[j+1]. If it is, they are in the wrong order for descending sort, so their positions are swapped using a temporary variable temp.
5. Print Result: After all passes, the str array contains the characters sorted in descending order, which is then printed.

Approach 2: Using Selection Sort

Selection Sort works by repeatedly finding the maximum element from the unsorted part of the array and putting it at the beginning.

• One-line summary: Finds the largest remaining character and places it at the correct position at the beginning of the unsorted subarray in each iteration.

// Sort String Descending (Selection Sort)
#include <stdio.h>
#include <string.h> // Required for strlen()

int main() {
    char str[] = "programming";
    int length = strlen(str);
    int i, j, max_idx;
    char temp;

    printf("Original string: %s\\n", str);

    // Step 1: Outer loop iterates through each position to place an element
    for (i = 0; i < length - 1; i++) {
        // Step 2: Assume the current element is the maximum
        max_idx = i;

        // Step 3: Inner loop finds the actual maximum element in the unsorted part
        for (j = i + 1; j < length; j++) {
            // Step 4: If a larger element is found, update max_idx
            if (str[j] > str[max_idx]) {
                max_idx = j;
            }
        }

        // Step 5: If the maximum element is not at the current position 'i', swap them
        if (max_idx != i) {
            temp = str[i];
            str[i] = str[max_idx];
            str[max_idx] = temp;
        }
    }

    // Step 6: Print the sorted string
    printf("Sorted string (descending): %s\\n", str);

    return 0;
}

Run

Sample Output:

Original string: programming
Sorted string (descending): rrpomniigg

Stepwise Explanation:

1. Initialize: A character array str and its length are defined.
2. Outer Loop: The for (i = 0; i < length - 1; i++) loop moves the boundary of the sorted part. i marks the current position where the next largest element will be placed.
3. Find Maximum: Inside the outer loop, max_idx is initially set to i. The inner loop for (j = i + 1; j < length; j++) then searches for the largest character in the *remaining unsorted part* of the string (from i+1 to length-1).
4. Update max_idx: If a character str[j] is found to be greater than str[max_idx], max_idx is updated to j.
5. Swap: After the inner loop completes, max_idx holds the index of the largest character in the unsorted segment. If max_idx is different from i (meaning the largest element is not already in its correct place), the character at str[i] is swapped with the character at str[max_idx].
6. Print Result: After all passes, the string str is sorted in descending order and printed.

Conclusion

Sorting a string in descending order involves rearranging its characters based on their ASCII values from largest to smallest. Both Bubble Sort and Selection Sort provide effective ways to achieve this without relying on complex library functions for character array sorting. While Bubble Sort is conceptually simple, Selection Sort can sometimes involve fewer swaps, though both have a time complexity of O(n²) for an array of n elements.

Summary

• String sorting in descending order arranges characters from highest ASCII value to lowest.
• Common manual algorithms like Bubble Sort and Selection Sort can be adapted for character arrays.
• Bubble Sort repeatedly compares and swaps adjacent elements to move larger characters to the front.
• Selection Sort finds the largest element in the unsorted portion and places it at the current position.
• Understanding basic loops, conditionals, and array manipulation is essential for implementing these sorts in C.