Modification of counting sort

Question

The Counting sort below sorts elements based on their ASCII value. The code below works fine but I want to do some I/O modification. The code doesn't take custom input.

I tried to do some changes but getting undefined behavior. My first doubt is why I'm getting undefined behavior. secondly, Please provide me with the code which will make the below code run as expected. The comment portion is what I tried by myself.I want it to take input from user.

#include<bits/stdc++.h>
#include<string.h>

using namespace std;

#define RANGE 255

void countSort(char arr[])      //void countSort(char arr[],int n)
{
    char output[strlen(arr)];   //char output[n];

    int count[RANGE + 1], i;
    memset(count, 0, sizeof(count));

    for(i = 0; arr[i]; i++) {
        count[arr[i]]++;
    }

    for (i = 1; i <= RANGE; ++i) {
        count[i] += count[i-1];
    }

    for (i = 0; arr[i]; ++i) {
        output[count[arr[i]]-1] = arr[i];
        --count[arr[i]];
    }

    for (i = 0; arr[i]; ++i) {
        arr[i] = output[i];
    }
}

// Driver code
int main()
{
    char arr[] = "geeksforgeeks";

    countSort(arr);

    cout<< "Sorted character array is "<<arr;

/*
    int n;
    cin>>n;
    char arr[n];

    for(int i=0;i<n;i++) {
        cin>>arr[i];
    }
    countSort(arr,n);

    for(int i=0;i<n;i++) {
        cout<<endl<<arr[i];
    }
*/
    return 0;
}

Answer 1

So the OP asked, how to take an input from the user and sort this. And not a predefined string in a given char array.

I will give the answer. But the question is tagged with C++, and I will convert it to C++.

By the way. The code in the question is a one to one copy from GeeksforGeeks and tries to code the so called Counting Sort algorithm in C++ that is described here.

Since the code is taken from GeeksforGeeks I unfortunately need to blame user "rathbhupendra" for really bad C++ code. I am truly sorry.

The code is using:

• C-Style arrays
• Variable Length Arrays (Compiler extension. Not C++ compliant)
• strlen
• memset
• #include<bits/stdc++.h> and #include<string.h>
• using namespace std
• unusal end conditions in for loops for(i = 0; arr[i]; ++i)
• char arrays instead of std::strings
• a Macro to define an array size (#define RANGE 255)

So, nothing C++.

And now, the answer.

You need to read the string from the user in a variable of type std::string with the function std::getline.

A std::string can be used like a character array. No difference.

Please see the C++ solution:

EDIT

Edited on the comments of MichaelDorgan

#include <iostream>
#include <string>
#include <vector>

constexpr size_t AsciiRange = 256;

// Convert signed char to unsigned size_t type.
inline size_t char2sizet(char c) { return static_cast<size_t>(static_cast<unsigned char>(c)); }

void countSort(std::string& stringToSort)      
{
    std::vector<size_t> count(AsciiRange, 0U);

    size_t i { 0U };
    for (i = 0U; i < stringToSort.size(); i++) {
        count[char2sizet(stringToSort[i])]++;
    }

    for (i = 1U; i < AsciiRange; ++i) {
        count[i] += count[i - 1U];
    }

    std::string output(stringToSort);  
    for (i = 0U; i < stringToSort.size(); ++i) {
        output[count[char2sizet(stringToSort[i])] - 1U] = stringToSort[i];
        --count[char2sizet(stringToSort[i])];
    }

    stringToSort = output;
}

int main()
{
    std::cout << "\nPlease enter a string:\n\n";

    // Get the string from the user
    std::string inputString{};
    getline(std::cin, inputString);

    // Sort it by characters
    countSort(inputString);

    // Show result
    std::cout << "\n\n\nString sorted by characters is:\n\n" << inputString << '\n';

    return 0;
}

Hope this helps . . .

Answer 2

I geuss by 'getting undefined behavior' you meant segmentation fault which sometimes occured. The problem lies in this line

for(i = 0; arr[i]; i++)

instead you should write

for(i = 0; i < n; i++)

You can check that in the first case at the end of each loop arr[i] is sometimes some weird character(this character doesn't belong to the input string) and count[arr[i]] for this char returns negative number which produce segmentation fault here

output[count[arr[i]]-1] = arr[i];