CODEWITHSUNDEEP
c++algorithmsortingvector
Badonka
Badonka

Reputation: 3

Why does my counting sort algorithm not sort at all?

#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

Upvotes: 0

Views: 115

Answers (1)

bitmask
bitmask

Reputation: 34626

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.

Upvotes: 4

Related Questions