В Руководстве по разработке алгоритмов существует такой акциз
4-26 Рассмотрим задачу о сортировке последовательности из n 0s и 1s, используя сравнения. Для каждого сравнения двух значений x и y алгоритм узнает, какой из x < y, x = y или x > y.
(a) Дайте алгоритм для сортировки в n - 1 сравнениях в худшем случае. Покажите, что ваш алгоритм оптимален.
(b) Дайте алгоритм сортировки в 2n/3 сравнениях в среднем случае (при условии, что каждый из n входов равен 0 или 1 с равной вероятностью). Показать что ваш алгоритм оптимален.
Для (a), я думаю, это довольно легко. Я могу выбрать [n-1] как точку опоры, затем сделать что-то вроде раздела quicksort, отсканировать от 0 до n - 2, найти среднюю точку, где левая сторона - все 0, а правая сторона - все 1, это займет n - 1 сравнение.
Но для (б) я не могу понять. Он говорит "каждый из n входов равен 0 или 1 с равной вероятностью" , поэтому, я думаю, я могу предположить, что числа 0 и 1 равны? Но как я могу получить результат, связанный с 1/3? разделите весь массив на 3 группы?
Спасибо
