查找计数排序的起始索引

Question

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



void sortByGroupById2(Student students[], int len) {
    int numberofschools = 7;
    int counters[numberofschools];

    for (int i = 0; i < numberofschools; i++) {
        counters[i] = 0;
    }

    for (int i = 0; i < numberofschools; i++) {
        counters[schoolToIndex(students[i].getSchool())]++;
    }

    Student *sortedArray = new Student[len];

    for (int i = 0; i < len; i++) {
    sortedArray[counters[schoolToIndex(students[i].getSchool())]] = students[i];
    counters[schoolToIndex(students[i].getSchool())]++;
    }

    for (int i = 0; i < len; i++) {
        students[i] = sortedArray[i];
    }

}

int main() {
    const int LEN = 350000;

    // Rough timing
    Student* uc2 = readStudentsFromFile("uc_students_sorted_by_id.txt", LEN);
    time(&start);
    sortByGroupById2(uc2, LEN);
    time(&end);
    cout << "Using counting sort it took " << difftime(end, start) << " seconds." << endl;

    writeStudentsToFile(uc1, LEN, "uc_by_school_by_id1.txt");
    writeStudentsToFile(uc2, LEN, "uc_by_school_by_id2.txt");
    return 0;
}

我遇到的具体问题在代码中

 sortedArray[counters[schoolToIndex(students[i].getSchool())]] = students[i],

我的起始索引sortedArray是学校的学生人数。我不确定如何做的是让起始索引为之前学校的学生累计数。

例如，如果我想要 UCLA 的起始索引，我需要将 UCB 和 UCD 以及 UCI 的学生人数相加以获得该桶的起始索引。

所以我的行动计划是让计数器数组存储学生人数的组合值。例如，如果我的计数器数组有 [5, 10, 15, 20] 作为学生人数，我希望它存储 [5, 15, 30, 50] 作为我的 sortedArray 的起始索引数组。

有什么方法可以用吗？我使用递归吗？

Answer 1

计数排序的一部分是对 counters[] 数组的转换，从简单的 直方图 到 索引再到 sortedArray[].

为此，您可以使用一种名为 partial sums 的算法。

对于每个元素，使其等于所有先前元素加上该元素的总和。例如：

0 1 3 0 4 0   -->    0 1 4 4 7 7

（您可以手动完成或使用 <numeric> 中的 std::partial_sum() 函数。）

现在您可以使用索引将内容移动到输出中的最后位置。为了保持稳定，从 students[] 中的 last 元素开始，并在 ~~histogram~~ 输出索引数组中查找它。

从值中减一（修改输出索引）并将源元素复制到最终数组：

for (int i = len; i-->0; )
{
    sortedArray[ --counters[ students[i].getSchool() ] ] = students[i];
}

希望对您有所帮助。

Answer 2

对于起始索引数组，您可能希望以 [0,5,15,30] 结束（请注意未使用最后计数 20）。为此，您可以使计数器大 1 个元素，或者您可以使用两个计数变量。计数需要扫描所有学生，这是 len，而不仅仅是学校的数量。

使用两个临时变量，sum 和 cnt:

    for (int i = 0; i < len; i++) {
        counters[schoolToIndex(students[i].getSchool())]++;
    }

    sum = 0;
    for (int i = 0; i < numberofschools; i++) {
        cnt = counters[schoolToIndex(students[i].getSchool())];
        counters[schoolToIndex(students[i].getSchool())] = sum;
        sum += cnt;
    }

如果你让计数器大一：

    int counters[numberofschools+1];
    // ...
    for (int i = 0; i <= numberofschools; i++) {
        counters[i] = 0;
    }
    for (int i = 0; i < len; i++) {
        // note the [1 + ...] only used here, not later in the actual sort
        counters[1+schoolToIndex(students[i].getSchool())]++;
    }
    for (int i = 2; i <= numberofschools; i++) {
        counters[schoolToIndex(students[i  ].getSchool())] += 
        counters[schoolToIndex(students[i-1].getSchool())];
    }

在任何一种情况下，都不使用最后的计数/索引，因为这是数据末尾的索引，并且该数组将用作起始索引的数组。

排序将从第一个元素开始到最后一个元素结束。我看到另一个答案是从最后一个元素开始向后遍历到第一个元素的替代方法，这也是稳定的，但不像从第一个元素开始那样缓存友好。

查找计数排序的起始索引

Finding the beginning index for counting sort

c++

sorting

bucket-sort

counting-sort