Нахождение начального индекса для подсчета сортировки

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.

Есть ли способ, который я могу использовать для этого? Я использую рекурсию?

0

bucket-sort c++counting-sort sorting

Решение

Другие решения

Часть счетной сортировки является преобразованием counters[] массив из простого гистограмма в индексы в sortedArray[].

Для этого вы используете алгоритм под названием частичные суммы.

Для каждого элемента сделайте его равным сумме всех предыдущих элементов плюс этот элемент. Например:

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

(Вы можете сделать это вручную или использовать std::partial_sum() функция в <numeric>.)

Теперь вы можете использовать индексы, чтобы переместить вещи в последнее место в выводе. Чтобы сохранить стабильность, начните с прошлой элемент в students[] и посмотреть в ~~гистограмма~~ массив выходных индексов.

Вычтите одно из значения (модифицируя выходные индексы) и скопируйте исходный элемент в окончательный массив:

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

Надеюсь это поможет.

2

Источник

Accepted Answer

Что касается массива начальных индексов, то, что вы, вероятно, захотите получить, это [0,5,15,30] (обратите внимание, что последний счет 20 не используется). Вы можете сделать счетчики на 1 элемент больше, чтобы сделать это, или вы можете использовать две переменные счета. Подсчетам необходимо сканировать всех учащихся, а не только количество школ.

используя две временные переменные, 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())];
}

В любом случае, последний счетчик / индекс не используется, поскольку это индекс до конца данных, а массив должен использоваться как массив начальных индексов.

Сортировка будет стабильной, начиная с первого элемента и заканчивая последним элементом. Я вижу другой ответ с альтернативным методом, начиная с последнего элемента, проходящего назад к первому элементу, который также стабилен, но не так удобен для кэша, как запуск с первого элемента.

0