Алгоритмы: разделить и покорить (применение быстрого сортировки ?!)

Question

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

Вы являетесь TA для класса с зачислением русских студентов. У вас есть их окончательные баллы (несортированные), и вы должны присвоить им один из доступных классов G (A, B, C и т. Д.). Эти ограничения (предполагается, что п является кратным G):

• Ровно (п/G), студенты получают каждый класс (для Например, если N = 30, а G = {A, B, C}, , то ровно 10 учеников получают A, 10 получить B и 10 получить C)
• Студент с более низким счетом не получает более высокий класс, чем студент с более высоким счетом (однако они могут получить тот же класс) Предполагая, что каждый ученик получил другой балл, вывести эффективный алгоритм и дать его сложность в терминах n и G. Любой алгоритм, который сначала сортирует оценки, получит z ero кредит.

Мой ответ: Хорошо, последняя строка проблемы говорит я не хорошо, если я пытаюсь сортировать массив первого и разделить массив в G равные части. Это займет O (n log n), когда используется лучший алгоритм сортировки. Итак, я подумал о сложном решении. Я рассматриваю эту проблему как пример, где быстрая сортировка может пригодиться, так как нам не нужны ученики, принадлежащие к одному классу, которые будут отсортированы. У нас может быть k основных элементов, а ключевые элементы - на одинаковом расстоянии. Но нам не дают оценки учеников, и нам также говорят, что у каждого ученика есть отчетливые оценки.

Прежде всего, я вычисляю максимальную и минимальную оценку, используя алгоритм Divine и Conquer MaxMin, который займет время O (n). Используя Максимум и Минимум, мы можем приблизительно найти ключевые элементы для каждого класса, вычислив. (Max-Min)/k = самый низкий класс, 2 * (Макс-Мин)/k = 2-й низкий класс. и k-1 * (Max-Min)/k = высшая оценка.

Теперь, используя эти элементы в качестве основных элементов, мы можем выполнить только метод разбиения для быстрого сортировки, который в первый раз принимает n времени, n- (Max-Min)/k во второй раз и т. Д. Таким образом, временная сложность алгоритма будет O (n), так как проблема min-max имеет сложность O (n), а раздел в Quick sort имеет сложность O (n).

Пожалуйста, поделитесь своими мыслями.

Answer 1

Вы можете поместить все баллы в очередь приоритетов (max), а затем извлечь из него группы n/G. Это по-прежнему неявная сортировка, но тем не менее не запрещается правилами.

Answer 2

Это в основном проблема выбора, только потому, что вы сразу выбираете G.

Модификация http://en.wikipedia.org/wiki/Quickselect Алгоритм должен работать здесь. Хотя Quicksort всегда рекурсивно спускается в оба раздела, а исходный Quickselect только опускается в тот, который содержит k-й индекс, алгоритм для этой проблемы должен опускаться в раздел тогда и только тогда, когда он содержит один из массивов ,, ... (G-1)*n/G индексы - те, которые разделяют точки между оценками.

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