Why is this counting sort not working?

#include <bits/stdc  .h>

using namespace std;

void countSort(vector<int>& input)
{
    int max = *max_element(input.begin(), input.end());
    vector<int> counter(max   1);
    vector<int> output;
    for(int i = 0; i < max   1;   i)
    {
        counter[i] = 0;
    }

    for(int i = 0; i < input.size();   i)
    {
        counter[input[i]]  ;
    }

    for(int i = 0; i < max    1;   i)
    {
        while(counter[i] > 0)
        {
            output.push_back(counter[input[i]]);
            counter[i]--;
        }
    }
}

int main()
{
    vector<int> array = {9, 8, 9, 1, 5, 7, 1, 2};
    countSort(array);
}

When I run this code, it just send me an error message,

The process finished with exit code 1073741819 (0xC0000005)

but I can't understand where the mistake is.

CodePudding user response：

The main problem is in your push_back.

output.push_back(counter[input[i]]);

It should simply be:

output.push_back(i);

You also do not save the result of the sorted output array. You could return it or replace input. In my example below, I'm replacing input.

Another potential problem is that you are sorting signed integers so you should expect negative ones. If you get a negative value now, you'll access your counter array out of bounds.

A simple remedy is to check for both the min and max values first and to subtract min from all subscripting in counter.

Example:

#include <algorithm>
#include <iostream>
#include <vector>

void countSort(std::vector<int>& input) {
    auto[minit, maxit] = std::minmax_element(input.begin(), input.end());
    auto min = *minit;
    auto max = *maxit;
    std::vector<int> counter(max - min   1);

    for(auto in : input)   counter[in-min];           // -min offset

    input.clear(); // clearing it to fill with the sorted values

    for(int i = min; i <= max;   i) {
        for(;counter[i-min] > 0; --counter[i-min]) {  // -min offset
            input.push_back(i);
        }
    }
}

int main() {
    std::vector<int> array = {9, 8, 9, 1, 5, 7, 1, 2, -10}; // negative value added
    
    countSort(array);

    for(auto v : array) std::cout << v << ' ';
}

Output:

-10 1 1 2 5 7 8 9 9