稳定计数在C中排序列表 [英] Stable counting sort a list in C

问题描述

如何对与分数关联的ID数组进行稳定计数排序

设法对单个数组进行排序，如{1,3,2,1,5}，但无法管理在下面这样做



输入：

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]--;
    } 

}

推荐答案

您的错误是您错误地了解了function counting_sort 确实以及它需要哪些参数。第三个参数不是 SResult 的数组，正如您所说的那样，但是包含位置的 int 的数组排序后的条目。因此，main中的代码应如下所示：

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:

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");

另外：显然你的代码还处于试验阶段。您应该取消那些固定数组的大小，例如 freq 和 cfreq 中的 counting_sort function。

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.

这篇关于稳定计数在C中排序列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！