C++ implementing counting sort

Question

I am doing a non comparison based sort based on counting sort.

I have done a simulation on paper but I am having trouble actually coding it.

I know i need to create a count array and then after counting use another array that sums it up cumulatively and then with that make a new array that uses the cumulative sum to sort it. How can I get the count array to keep track? that part confuses me

Can anyone guide me in the right direction?

int schoolToIndex(string school) {
    if (school == "UCB")  return 0;
    if (school == "UCD")  return 1;
    if (school == "UCI")  return 2;
    if (school == "UCLA") return 3;
    if (school == "UCM")  return 4;
    if (school == "UCSD") return 5;
    if (school == "UCSF") return 6;

    cerr << "Unknown school " << school << endl;
    return -1;
}

/*
 * Sorts students by school. An implementation of counting sort.
 * @param students array already sorted by ID
 * @param len Array length
 */
void sortByGroupById2(Student students[], int len) {
    int temp[len];
    int count[7];

    // Creates an array where schools are converted to ints by using schoolToIndex
    for(int i = 0; i < len; i++) {
        temp[i] =schoolToIndex(students[i].getSchool());

    }

    for(int i =0; i < 7;  i++) {
        count[i]=0;
    }


    for(int j =0; j < len;  j++) {
        count[temp[j]]++;
        cout << j << " "  << count[j] << endl;

    }
}

test.txt file im using

 Joe Paarmann,10000010,UCSF
Otha Baloy,10000053,UCSD
Alton Hamblet,10000110,UCM
Jessie Merle,10000345,UCI
Lawanda Doell,10000455,UCM
Alva Zajicek,10000479,UCI
Chester Kemfort,10000529,UCD
Alice Mines,10000579,UCI
Gary Vongunten,10000875,UCM
Adrian Shbi,10001036,UCSD

Why do you want to calculate a cumulative sum? Maybe you question would be more clear if you would say a bit more about your actual use case. You have a set of students and you want to sort the schools with respect to how many students go to each of them, right? — 463035818_is_not_an_ai
– 463035818_is_not_an_ai, Commented Apr 30, 2015 at 9:16
Your count array better be seven items wide, no less. Start by getting the counts correct. Just get the school index in a tmp. If it is >= 0 (and for safety, < 7) just ++count[tmp];. When finished count[] will have the counts you need. That will at least get you started. — WhozCraig
– WhozCraig, Commented Apr 30, 2015 at 9:19
cumulative sum array is used to make the sorted array. I have a set of students that are already sorted by ID but I want them to be sorted by school name alphabetically and ID in ascending order. — Jorde Guevara
– Jorde Guevara, Commented Apr 30, 2015 at 9:24
If you want to use counting sort in particular (maybe its an assignment?) take a look here. If not, I would simply use std::sort. — 463035818_is_not_an_ai
– 463035818_is_not_an_ai, Commented Apr 30, 2015 at 9:30

Serge Ballesta · Accepted Answer · 2015-04-30 10:14:34Z

1

For counting sort, you first count how many students exist by school (first pass on array). Then you deduce the index of first student per school. And finally you store the students in right place in target array (second pass on array)

Counting sort is not an in-place sort, so you should pass another array to the function to get sorted values back.

/*
 * Sorts students by school. An implementation of counting sort.
 * @param students array already sorted by ID
 * @param len Array length
 */
void sortByGroupById2(Student students[], Student* sorted[], int len) {
    int count[6];

    // initialization
    for(int i=0; i<6; i++) count[i] = 0;

    // how many students by school
    for (int i=0; i<len; i++) {
        count[schoolToIndex(students[i].getSchool())]++
    }

    // convert number of students per school into index of first student
    int rank = 0, old;
    for (int i=0; i<6; i++) {
        old = count[i];
        count[i] = rank;
        rank += old;
    }

    // affect students in correct places
    for (int i=0; i<len; i++) {
        rank = count[students[i].getSchool()]++; // rank in sorted array will be current
               // value of count for the school (first place for first time) and that
               // value is incremented to be ready for next student for this school
        sorted[rank] = &Student[i];
    }
}

That way sorted countains pointers to Student sorted by school.

References : Wikipedia

answered Apr 30, 2015 at 10:14

Serge Ballesta

150k13 gold badges137 silver badges267 bronze badges

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

1 Comment

Jorde Guevara Over a year ago

my counter array comes out all messed up. I don't know why it's not counting

Collectives™ on Stack Overflow

C++ implementing counting sort

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related