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
– 1201ProgramAlarm, Commented Mar 18, 2020 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
– Adrian Mole, Commented Mar 18, 2020 at 20:33
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
– bitmask, Commented Mar 18, 2020 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
– drescherjm, Commented Mar 18, 2020 at 21:03

bitmask · Accepted Answer · 2020-03-18 21:52:45Z

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, 2020 at 21:52

answered Mar 18, 2020 at 21:28

bitmask

35.2k17 gold badges107 silver badges174 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Why does my counting sort algorithm not sort at all?

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related