Глава 4. Сортировка

4.2. Алгоритмы порядка n log n
   4.2.1. Предложить алгоритм сортировки, число действий которого было бы порядка n log n, то есть не превосходило бы C*n*log(n) для некоторого C и для всех n. Мы предложим два решения. Решение…
4.3. Применения сортировки
  4.3.1. Найти количество различных чисел среди элементов данного массива. Число действий порядка n*log n. (Эта задача уже была в главе о массивах.) Решение. Отсортировать числа, а затем посчитать…
4.4. Нижние оценки для числа сравнений при сортировке
  Пусть имеется n различных по весу камней и весы, которые позволяют за одно взвешивание определить, какой из двух выбранных нами камней тяжелее. (В программистских терминах: мы имеем доступ к функции…
4.5. Родственные сортировке задачи
  4.5.1. Какова минимально возможная сложность (число сравнений в наихудшем случае) алгоритма отыскания самого легкого из n камней? Решение. Очевидный алгоритм с инвариантом "найден самый легкий камень…
4.1. Квадратичные алгоритмы
  4.1.1. Пусть a[1], ..., a[n] - целые числа. Требуется построить массив b[1], ..., b[n], содержащий те же числа, для которого b[1] <= ... <= b[n]. Замечание. Среди чисел a[1]...a[n] могут быть…