Как отсортировать массив студенческих записей по их оценке

Question

Привет всем, я сейчас готовлюсь к экзамену, и я не могу понять эту концепцию.Вопрос в том, если вы предоставили массив записей о студентах, где членами записи являются имя студента и его оценка, как вы можете отсортировать его по классам.Профессор привел этот пример того, что он назвал «распределенным подсчетом».У меня проблемы с пониманием, и я надеялся, что кто-то может дать мне псевдокод или алгоритм для кода ниже, спасибо:)

Function Distribution_counting_sort(S, n){
//Input: a student array S of n records
//Output: a sorted array (wrt grade) NS
int count[101]; /*init to 0’s */
/* counting */
for (i = 0; i < n; i++) count[S[i].grade]++;
/* accumulating */
count[0]--;
for (i = 1; i < 101; i++) count[i] = count[i -1] + count[i];
/* distribution */
for (i = 0; i < n; i++) NS[count[S[i].grade]--] = S[i];

Answer 1

Это, по сути, вариация Сортировка ведер .

Это ведра, по одному на каждую возможную оценку:

int count[101]; /*init to 0’s */

Это подсчет количества учениковкаждый класс.Это говорит нам о размере каждого сегмента:

for (i = 0; i < n; i++) count[S[i].grade]++;

Это конвертирует количество в кумулятивные.Это дает нам конечную позицию каждого сегмента в массиве назначения.Я считаю, что бит count[0]-- предназначен для учета массивов на основе 0.

count[0]--;
for (i = 1; i < 101; i++) count[i] = count[i -1] + count[i];

Теперь он помещает каждого учащегося в конец его / ее сегмента и уменьшает значение позиции для этого блока.

for (i = 0; i < n; i++) NS[count[S[i].grade]--] = S[i];

Хорошая особенность такого рода сортировки в том, что это O (n), а не O (n * log (n)).Однако он работает только для вещей, которые могут быть дискретизированы в конечное (и управляемое) количество сегментов.

Одна вещь, которая немного забавна в этом коде, заключается в том, что он меняет порядок учеников, имеющих одинаковую оценку,Вы, вероятно, могли бы изменить его, чтобы он стал стабильным, изменив кумулятивные значения на начальные позиции сегмента и увеличивая их при заполнении NS, или, что еще проще, проходите через S назад в этом последнем цикле.

Answer 2

Есть 101 класс, 0 - 100

int count[101]; /*init to 0’s */

Заполните счет [] итоговыми данными по каждому классу, например, count [90] = 4 означает, что четыре человека получили 90%

for (i = 0; i < n; i++) count[S[i].grade]++;

Далее, конвертируйте эти итоги в бегущий подсчет, т.е. если 57 человек получили меньше 90, то посчитайте [90] = 57 + 4 или 61. Таким образом, для каждого подсчета [n] у вас есть количество людей кто получил эту оценку или ниже. Это важно для окончательного массива ... вам нужно 61 элемент в конечном массиве, чтобы вместить всех, кто получил 90 или ниже. Обратите внимание, что count [100] должен = n передан.

count [0] - сдвигает весь отсчет на единицу, что преобразует конечный массив на основе 1 в конечный массив на основе 0, например, если у меня есть один человек, который получил ноль, count [0] = 1, поэтому мой последний массив будет начинаться с NS [1]. Я хочу начать с NS [0]. Таким образом, 61 элемент выше теперь 60

count[0]--;
for (i = 1; i < 101; i++) count[i] = count[i -1] + count[i];

Наконец (если бы он прекратил повторное использование 'i'), найдите место для каждого класса ... если есть 60 человек с '90' или ниже, класс '90' входит в 60-й элемент окончательного массива NS Это сбивает с толку, отчасти из-за того, что «-» ... помните, что 60 для класса «90», поэтому первые «90», к которым вы придете, будут помещены в NS [60], потому что есть 59 люди с более низкими оценками. Счет для «90» уменьшен до 59, поэтому следующие «90» будут размещены в NS [59]. И так далее.

for (i = 0; i < n; i++) NS[count[S[i].grade]--] = S[i];

Конечный результат - массив с наименьшим или самым высоким баллом, где NS [0] является наименьшим, а NS [n] - наивысшим.

Имеет смысл? Это действительно красивый алгоритм!

Answer 3

Эта статья о сортировке может помочь.

http://www.cs.bu.edu/teaching/cs113/spring-2000/sort/