Я вот тут раскопал любопытную книжицу. В ней - олимпийские задания по программированию за 8 первых Московских олимпиад.
Это значит меня из школы куда-то отправляли и готовился я по этой книге. Году этак в 94-ом, если интересно.
В общем, есть алгоритмы и решения на Бейсике, Паскале, Си и Фортране. Так что желающим примериться к мерке 80-го года - добро пожаловать.
Интересно последнее задание. Новый массив не заводить.. А можно, я напишу цикл от 1 до n и заведу 3 переменных. пройду в цикле по всем элементам массива и посчитаю, сколько у меня нулей, единиц и двоек. А потом еще раз цикл от 1 до n где каддому элементу сначала присваиваю i нулей, потом j единиц, а потом k двоек. Такое решение считается?
как раз counting sort быстрее и эффективней в данном случае
сложность алгоритмов одинаковая (линейная), сортировка подсчетом проще в реализации и работает в других случаях, когда количество уникальных значений больше трех
Да, конечно, это самое эффективное решение поставленной задачи, сортировка подсчётом (counting sort).
Если мне память не изменяет, то она требует нескольких проходов по массиву. Но данная задача решается в один проход. Или я ошибаюсь?
Да, всё верно. Возможно, я был не прав на счёт «самый эффективный», не уверен. Дело в том, что сортировка подсчётом - два прохода, но dutch flag algorithm - один проход, но больше сравнений и есть swap. Скорее всего, примерно одинаково, если массив - действительно просто числа.
