Постановка задачи сортировки

Пусть задан некоторый набор данных, состоящий из N записей Х1,

Х2,..., ХN. Каждая запись Хi кроме информации содержит поле ключа

Кi. Требуется расставить записи в наборе данных в таком порядке

XL1, XL2, ..., XLN, чтобы для заданной функции сортировки F

было справедливо соотношение

F(XL1) < F(XL2) <...< F(XLN) или K(XL1) < K(XL2) <...< K(XLN).

Таким образом, сортировка (упорядочение) - это процесс

целенаправленной перестановки записей, при котором их взаимное

расположение в наборе данных приводится в порядок, определяемый

некоторым известным ключом. Функция сортировки F задает отношение

порядка. Порядок может быть алфавитный, хронологический, порядок

возрастания или убывания значений ключей и т.д.

В информационных системах некоторый набор данных хранится

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

говорит тот факт, что в информационных системах в среднем более 25 % машинного времени систематически тратится на сортировку.

Представьте, насколько трудно было бы пользоваться словарем, если

бы слова в нем не располагались в алфавитном порядке. Точно также от

порядка, в котором хранятся элементы в памяти ЭВМ, во многом зависит

скорость и простота алгоритмов, предназначенных для их обработки.

Сортировка называется устойчивой, если она удовлетворяет

условию, что записи с одинаковыми ключами при сортировке остаются в прежнем порядке, т.е. считается

F(XLi) < F(XLj), если K(XLi)=K(XLj) при i < j.