Write A Program To Sort A String In Alphabetical Order In C Program

Sorting strings alphabetically is a common task in programming, useful for organizing data, performing lexicographical comparisons, and preparing text for further analysis. This operation arranges the characters within a given string in ascending order based on their ASCII values.

In this article, you will learn how to implement string sorting in C using two distinct approaches: the fundamental Bubble Sort algorithm and the efficient standard library qsort() function.

Problem Statement

The core problem is to rearrange the characters of a given string such that they appear in alphabetical order. For example, if the input string is "programming", the output should be "aggimmnoprr". This task is crucial in various applications where data needs to be presented or processed in a standardized, sorted manner. Without an effective sorting mechanism, comparing strings lexicographically or performing operations like anagram detection becomes significantly more complex.

Background & Knowledge Prerequisites

To effectively understand and implement string sorting in C, you should have a basic understanding of:

• C Strings: How strings are represented as null-terminated character arrays.
• Arrays: Accessing and manipulating elements within arrays.
• Loops: for and while loops for iteration.
• Pointers: Basic understanding of pointer arithmetic and how they relate to arrays.
• Functions: Declaring, defining, and calling functions.
• ASCII Values: How characters are represented numerically.

Relevant header files typically include stdio.h for input/output, string.h for string manipulation functions (like strlen), and stdlib.h for general utilities like qsort().

Use Cases

Sorting strings alphabetically has numerous practical applications across various domains:

• Lexicographical Ordering: Arranging a list of words or names in dictionary order, such as in contact lists or file explorers.
• Anagram Detection: To determine if two strings are anagrams of each other, one can sort both strings and then compare them. If the sorted strings are identical, they are anagrams.
• Data Normalization: Standardizing data entries by sorting characters within a string can help in data cleaning and ensuring consistency for comparisons or storage.
• Frequency Analysis: When characters are sorted, identical characters are grouped together, making it easier to count their occurrences or identify patterns.
• Text Processing Utilities: Used in search algorithms, text indexing, and various linguistic analyses where the internal order of characters matters.

Solution Approaches

We will explore two robust methods for sorting a string in C: implementing a basic sorting algorithm (Bubble Sort) and utilizing the powerful qsort() function from the standard library.

Approach 1: Bubble Sort Algorithm

This approach involves iteratively comparing adjacent characters and swapping them if they are in the wrong order, effectively "bubbling up" the largest characters to their correct positions.

One-line summary: Compares and swaps adjacent characters repeatedly to move larger elements to the end of the string.

// String Sort with Bubble Sort
#include <stdio.h>
#include <string.h> // For strlen

int main() {
    char str[] = "programming";
    int length = strlen(str);

    // Step 1: Outer loop for passes
    for (int i = 0; i < length - 1; i++) {
        // Step 2: Inner loop for comparisons and swaps
        for (int j = 0; j < length - 1 - i; j++) {
            // Step 3: Compare adjacent characters
            if (str[j] > str[j+1]) {
                // Step 4: Swap if characters are in wrong order
                char temp = str[j];
                str[j] = str[j+1];
                str[j+1] = temp;
            }
        }
    }

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

    return 0;
}

Run

Sample Output:

Original string: programming
Sorted string: aggimmnoprr

Stepwise Explanation:

1. Initialize String and Length: A character array str is declared, and its length is determined using strlen().
2. Outer Loop (i): This loop controls the number of passes required. In each pass, at least one character is placed in its final sorted position. It runs length - 1 times.
3. Inner Loop (j): This loop iterates through the unsorted part of the string. The length - 1 - i adjustment optimizes the loop by not re-checking elements already placed at the end.
4. Comparison: if (str[j] > str[j+1]) compares two adjacent characters. In C, characters are implicitly converted to their ASCII values for comparison.
5. Swap: If the character at j is greater than the character at j+1, they are swapped using a temporary variable temp. This ensures that the smaller character moves to the left.
6. Print Result: After the loops complete, the str array contains the alphabetically sorted string, which is then printed.

Approach 2: Using the qsort() Standard Library Function

The qsort() function is a powerful, generic sorting function provided by the C standard library (stdlib.h). It implements a quicksort algorithm, which is generally more efficient than bubble sort for larger datasets.

One-line summary: Uses the standard C library's quicksort implementation with a custom comparison function to sort the characters in a string.

// String Sort with qsort()
#include <stdio.h>
#include <string.h> // For strlen
#include <stdlib.h> // For qsort

// Step 1: Custom comparison function for characters
int compareChars(const void *a, const void *b) {
    return (*(char*)a - *(char*)b);
}

int main() {
    char str[] = "programming";
    int length = strlen(str);

    // Step 2: Call qsort function
    // Parameters:
    //   - str: Pointer to the array to be sorted
    //   - length: Number of elements in the array
    //   - sizeof(char): Size of each element
    //   - compareChars: Pointer to the comparison function
    qsort(str, length, sizeof(char), compareChars);

    // Step 3: Print the sorted string
    printf("Original string: programming\\n");
    printf("Sorted string: %s\\n", str);

    return 0;
}

Run

Sample Output:

Original string: programming
Sorted string: aggimmnoprr

Stepwise Explanation:

1. Include Headers: stdio.h for I/O, string.h for strlen, and stdlib.h for qsort().
2. Define compareChars Function: qsort() requires a comparison function that takes two const void* pointers as arguments. This function should return:
   • A negative value if the first element is less than the second.

Zero if the elements are equal.

A positive value if the first element is greater than the second.

In our compareChars function, we cast the void pointers back to char*, dereference them to get the actual characters, and subtract them. This directly yields the required negative, zero, or positive result based on ASCII values.

1. Call qsort():
   • The first argument (str) is a pointer to the beginning of the array to be sorted.

The second argument (length) is the number of elements in the array.

The third argument (sizeof(char)) is the size of each element in bytes.

The fourth argument (compareChars) is a pointer to our custom comparison function.

1. Print Result: After qsort() completes, the str array is sorted alphabetically, and the result is printed.

Conclusion

Sorting a string in alphabetical order in C can be achieved through various methods, each with its own advantages. The Bubble Sort algorithm offers a clear and intuitive way to understand the underlying mechanics of comparison and swapping, making it excellent for educational purposes. For practical applications requiring efficiency, the qsort() function from the standard library provides a robust and highly optimized solution, abstracting away the sorting algorithm details behind a generic interface. Choosing the right approach depends on the specific requirements for performance, code readability, and the scale of the data being processed.

Summary

• Problem: Rearranging string characters alphabetically based on ASCII values.
• Bubble Sort:
• Mechanism: Iteratively compares and swaps adjacent characters.
• Pros: Simple to understand and implement.
• Cons: Less efficient for larger strings (O(n^2) time complexity).
• qsort() Function:
• Mechanism: Standard C library function implementing quicksort; requires a custom comparison function.
• Pros: Highly efficient (average O(n log n) time complexity), versatile for sorting any data type.
• Cons: Requires understanding of void pointers and function pointers for the comparison function.
• Use Cases: Essential for lexicographical ordering, anagram detection, data normalization, and various text processing tasks.