Информатика и ИИ · эксперимент
Сортировка без сравнения всего со всем
Кандидаты, рекомендатели, граф разрешённых сравнений и оценка, которая держалась с 2011 года. Четыре вопроса, от начального уровня до продвинутого, о том, как сортировать, когда некоторые пары нельзя сравнить.
1 · Правило2 · Фазы3 · QuickSort4 · Ещё открыто
1 · Найди, что меняется
Начальный
Чем обобщённая сортировка отличается от обычной сортировки?
2 · Посчитай фазы
Каждая фаза алгоритма даёт догадку как минимум для половины ещё не обработанных связей и откладывает остальные. В графе около миллиона связей, примерно 2²⁰.
Средний
Сколько примерно фаз нужно самое большее, чтобы у каждой связи появилась догадка?
3 · Найди, что ломает QuickSort
Продвинутый
Почему метод в духе QuickSort нельзя просто применить к обобщённой сортировке?
4 · Найди, чего статья не даёт
Продвинутый
Чего из этого статья не даёт?
Порядок восстановлен
—