Программирование на языке высокого уровня. Марапулец Ю.В. - 45 стр.

-   алгоритмы рекурсивного поиска, основанные на полном переборе вариантов (будут
    рассмотрены далее), имеют обычно показательную зависимость трудоемкости от
    размерности входных данных (mN).




                      Рис.2.2. Трудоемкость алгоритмов сортировки и поиска.

      Алгоритм двоичного поиска работает только в том случае, если элементы отсорти-
рованы. Если по одному и тому же набору данных планируется неоднократный повтор-
ный поиск, то выгоднее один раз отсортировать данные, а затем использовать двоичный
поиск. Если набор данных известен заранее, то он может быть отсортирован при напи-
сании программы и проинициализирован во время компиляции. В противном случае не-
обходимо производить сортировку во время выполнения программы.
      Алгоритмы сортировки можно классифицировать по нескольким признакам [10].
      Вид сортировки по размещению элементов: внутренняя - в памяти, внешняя - в
файле данных.
      Вид сортировки по виду структуры данных, содержащей сортируемые эле-
менты: сортировка массивов, массивов указателей, списков и других структур данных.
      Существует достаточно большое количество алгоритмов сортировки. Рассмотрим
основные виды. Прежде всего, выделим сортировки, в которых в процессе работы созда-
ется упорядоченная часть - размер ее увеличивается на 1 за каждый шаг внешнего цикла.
Сюда относятся две группы сортировок:
• сортировка выбором: выбирается очередной минимальный элемент и помещается в
    конец последовательности;
• сортировка вставками: очередной элемент помещается по месту своего располо-
    жения в выходную последовательность (массив).
      Две другие группы используют разделения на части, но по различным принципам и
с различной целью:
• сортировка разделением: последовательность (массив) разделяется на две частично
    упорядоченные части по принципу «больше-меньше», которые затем могут быть от-
    сортированы независимо (в том числе тем же самым алгоритмом);
• сортировка слиянием: последовательность регулярно распределяется в несколько
    независимых частей, которые затем объединяются (слияние).
      Сортировки этих групп отличаются от «банальных сортировок» тем, что процесс
упорядочения в них в явном виде не просматривается.
      Отдельная группа обменных сортировок с многочисленными оптимизациями ос-
нована на идее регулярного обмена соседних элементов.


                                            45