[OTHER]sorting/counting_sort_string.cpp:17

[18781875724]

What would you like to share?

Issue: Out-of-Bounds Access in Counting Sort Implementation

Problem Description

The countSort function contains critical out-of-bounds access issues. The output string is declared empty but accessed via output[count[arr[i]] - 1] = arr[i], causing undefined behavior. The string has zero length initially, but the algorithm writes to arbitrary positions without pre-allocation.

Root Cause

• string output is initialized with length 0
• No memory allocated before writing to specific indices
• Algorithm treats empty string like pre-allocated character array

Impact

• Program crashes or segmentation faults
• Memory corruption and unpredictable behavior
• Incorrect sorting results
• Potential security vulnerabilities

Steps to Reproduce

1. Compile and run the program
2. Enter any non-empty string (e.g., "hello")
3. Observe crash or incorrect output

Suggested Fix

void countSort(string& arr) {
    int n = arr.length();
    string output(n, ' ');  // Pre-allocate with correct size
    
    int count[256] = {0};
    for (int i = 0; i < n; ++i) 
        ++count[(unsigned char)arr[i]];
    
    for (int i = 1; i < 256; ++i) 
        count[i] += count[i - 1];
    
    for (int i = 0; i < n; ++i) {
        output[count[(unsigned char)arr[i]] - 1] = arr[i];
        --count[(unsigned char)arr[i]];
    }
    
    arr = output;
    cout << "Sorted character array is " << arr;
}

### Additional information

_No response_