Общие понятия СОРТИРОВКА И ПОИСК

.

Общие понятия СОРТИРОВКА И ПОИСК

Сортировка – это процесс упорядочения элементов массива или списка по возрастанию или убыванию.

Существует много алгоритмов сортировки, отличающихся по ряду характеристик:

·               Время работы, или вычислительная сложность – количество операций, затрачиваемых алгоритмом. Обычно оценивается худший сценарий, когда исходный массив оказывается максимально неупорядо- чен с точки зрения алгоритма.

·               Затрачиваемая память (помимо исходного массива) – неко- торые алгоритмы требуют выделения дополнительной памяти для вре- менного хранения данных или формирования нового выходного масси- ва.

Кроме того, алгоритмы можно разделить по типу доступа к дан- ным:

·               Алгоритмы внутренней сортировки применяются для сорти- ровки данных, целиком находящихся в оперативной памяти.

·               Алгоритмы внешней сортировки оперируют данными, не по- мещающимися в оперативную память. Такие алгоритмы используют внешнюю память, доступ к которой требует существенно большего времени, поэтому требуются специальные алгоритмические решения, чтобы каждый элемент использовался алгоритмом минимальное коли- чество раз.