Click here to Skip to main content
15,860,859 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
How to have a Stable counting sort for a array of ID associated with the score
manage to sort a single array like {1,3,2,1,5} but does not manage to do it for below

Input:

int main()
{
    //Note: The sample is sorted by "student id"
    struct SResult sample[] = {
        {"A1234", 10},
        {"A1239", 5},
        {"A1394", 7},
        {"A1434", 3},
        {"A1454", 5},
        {"A2884", 7},
        {"A3235", 7},
        {"A4334", 9},
        {"A4884", 2},
        {"A6934", 5},
        {"A7265", 7},
        {"A9559", 3}
    };

    struct SResult sorted[12] = {{0}};
    int i;

    counting_sort(sample, 12, sorted);

    for (i = 0; i < 12; i++){
        printf("[%s, %d]\n", sorted[i].studentID, sorted[i].score);
    }
    printf("\n");

    return 0;
}


What I have tried:

struct SResult {
    char studentID[6];
    int score;
};


void counting_sort(struct SResult scoreArr[], int N, int final[])
{

    int freq[11] = {0}, cfreq[11] = {0};
    int i, curScore;

    //1. Compute Frquency
    for (i = 0; i < N; i++){
        freq[ scoreArr[i].score ] ++;
    }

    //2. Compute Cumulative Frequency
    cfreq[0] = freq[0];
    for (i = 1; i < 11; i++){
        cfreq[i] = cfreq[i-1] + freq[i];        
    }

    //3. Produce Final Position

    for (i = 0; i < N; i++){
        curScore = scoreArr[i].score;
        final[ cfreq[ curScore ] - 1 ]  = curScore;
        cfreq[curScore]--;
    } 

}
Posted
Updated 17-Mar-18 4:27am
v3
Comments
OriginalGriff 17-Mar-18 5:53am    
What have you done so far towards creating the list, sorting the list, etc.?
JiaWei Lee 17-Mar-18 6:52am    
tried what is code in What i have tried section
OriginalGriff 17-Mar-18 6:59am    
There is no list in that code - that's an array.
JiaWei Lee 17-Mar-18 8:07am    
yes it is an array
OriginalGriff 17-Mar-18 8:21am    
So why are you talking about lists, and what's the problem you are having?
It's important to be precise here: remember that we can't see your screen, access your HDD, or read your mind - we only get exactly what you type to work with. So if you talk about lists, we assume you mean a linked list, which is more complicated to work with than an array. Tell us what you mean, and explain what help you need and we'll do what we can.

1 solution

Your error is that you have the wrong idea about what the function counting_sort does and which arguments it takes. The third argument is not an array of SResult, as you assumend, but an array of int that contains the positions of the entries after sorting. Your code in main should therefore look like this:
C++
int sorted[12];
int i;
int k;

counting_sort(sample, 12, sorted);

for (i = 0; i < 12; i++){
    k = sorted[i];
    printf("[%s, %d]\n", sample[k].studentID, sample[k].score);
}
printf("\n");

Also: Obviously your code is just in the experimental stage. You should do away with those fixed array sized like the one for freq and cfreq in your counting_sort function.
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900