Why does my counting sort algorithm not sort at all?

Question

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

using namespace std;

void SortCount(vector<int>& vec){
    int max_el = *max_element(vec.begin(), vec.end());

    vector<int> C(max_el+1, 0);
    vector<int> B(vec.size(), 0);

    for(int i = 0; i < vec.size(); i++){
        C[vec[i]] = C[vec[i]] + 1;
    }
    for(int i = 1; i <= vec.size(); i++){
        C[i] = C[i] + C[i - 1];
    }
    for(int i = 0; i < vec.size(); i++ ) {
        B[C[vec[i]] - 1] = vec[i];
        C[vec[i]] = C[vec[i]] - 1;
    }
    for(int i=0; i<vec.size(); i++){
        vec[i] = B[i];
    }
}

int main() {

    vector<int> vec {5,2,43,31,67,311};
    SortCount(vec);

    for (size_t i=0;  i <vec.size();  i++) {
        cout<<vec[i]<<" ";
    }

    return 0;
}

I did exactly by the book but for some reason it just prints out the values in the same orders they were placed in. Where did I mess up?

Edit: I added the main function

You find `max_el`, but never use it anywhere. Perhaps this is a problem? — 1201ProgramAlarm, Mar 18 '20 at 20:31
I don't see *anywhere* in your code where you actually change (or even assign anything to) any element of the given `vec` argument! You're just changing (maybe) things in local copies. — Adrian Mole, Mar 18 '20 at 20:33
I edited the code, accidentally used the experimental thing I tried. I use the max_el. — Badonka, Mar 18 '20 at 20:35
Please try to post *the exact code* you are asking questions about. Cut and paste it from your code editor. It's hard to give meaningful help otherwise. — john, Mar 18 '20 at 20:53
Done. Mind is hazy because this has been bothering me for hours — Badonka, Mar 18 '20 at 20:54
I would love to but my assignment is to write a counting sort, so no cutting corners there. — Badonka, Mar 18 '20 at 20:57
I highly doubt using namespace std; is not making my count sort work. — Badonka, Mar 18 '20 at 21:00
It's not, which is why it's not an answer, but a comment. You appear to be learning C++, so the link might be valuable to you. — bitmask, Mar 18 '20 at 21:01
The point of someone posting that link is to try to urge you to break this bad practice now before it hurts you in the future. No it's not causing the problem. — drescherjm, Mar 18 '20 at 21:03

bitmask · Accepted Answer · 2020-03-18T21:52:45.930

4

Your iteration over the count array has the wrong bounds:

//for(int i = 1; i <= vec.size(); i++) { <--wrong
for(int i = 1; i < C.size(); i++) {
    C[i] = C[i] + C[i - 1];
}

Also you should get in the habit of using std::size_t as a type for an index instead of int. int is both too small and also is signed, so it is unsuited for indices.

edited Mar 18 '20 at 21:52

answered Mar 18 '20 at 21:28

bitmask

32,434
14
99
159

Why does my counting sort algorithm not sort at all?

1 Answers1