SelectionSort. Однако,
SelectionSort. Однако, рассматривая более "мелкие" операции, мы обнаружим, что их количество уже зависит от контекста, и реальное время выполнения сортировок векторов окажется неодинаковым. Какой из векторов будет обработан быстрее всех, а какой - медленнее остальных?
Упражнение #3.
Эта задача предлагалась школьникам на городской олимпиаде по информатике в Санкт-Петербурге, точнее, еще в Ленинграде. Задан массив Mas[1..N], состоящий из 0, 1 и 2. Требуется перестроить его таким образом, чтобы все 0 оказались в начале массива, далее - все 1 и в конце - все 2. Можно ли обойтись одним просмотром массива?
Как мы до сих пор ни старались, асимптотическая трудоемкость всех рассмотренных выше модификаций обменной сортировки оставалась одной и той же - квадратичной. Однако возможности улучшить эту оценку есть.
Вспомним один из общих алгоритмических подходов к задаче, обсуждавшийся нами в Уроке A3, а именно, метод частных целей. Сейчас, как мы увидим, подходящей случаю окажется
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
