3. Алгоритмы сортировки

   1. Введение

Почти во всех машинных приложениях множество объектов должно быть размещено в соответствии с некоторым заранее определенным порядком. Например, расположить данные по алфавиту или по возрастанию номеров.

Пусть имена x₁, …, x_n заданы в виде таблицы. Каждое имя x_i принимает значение из пространства имен, на котором определен линейный порядок. Далее мы считаем, что никакие 2 имени не имеют одинаковых значений, т.е. любые x_i, x_j обладают тем свойством, что если i  j, то либо x_i предшествует x_j, либо наоборот [3].

Ограничение x_i  x_j при i  j упрощает анализ без потери общности, т.е. корректность идей и алгоритмов не нарушается. Цель сортировки состоит в том, чтобы выполнить перестановку , для которой.

В задачах частичной сортировки требуется извлечь либо частичную информацию о П (например, _i для нескольких значений i), либо полностью определить П по заданной частичной информации о ней (так обстоит дело при слиянии двух упорядоченных таблиц).С каждой записью x_i в последовательности x₁, …, x_n сопоставим некоторый ключ ‘k’. Ключом обычно является некоторое поле внутри записи. Говорят, что файл отсортирован по ключу, если для i < j следует, что k_i предшествует k_j при некоторой упорядоченной последовательности по ключам. В качестве примера рассмотрим телефонный справочник. Файл состоит из всех строчек этого справочника. Каждая строчка является записью. Ключом, по которому отсортирован этот файл, является поле фамилия в записи. Каждая запись содержит также поле для адреса и номера телефона.

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

Вполне возможно, что две записи в некотором файле имеют одинаковый ключ. Метод сортировки называется устойчивым, если для всех записей i и j таких, что k(i) = k(j), выполняется условие, что в отсортированном файле x_i предшествует x_j, если x_i предшествует x_j в первоначальном файле.

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

Пример.

а) первоначальный файл б) отсортированный файл

ключ	информация		ключ	информация
4	DDD		1	AAA
2	BBB		2	BBB
1	AAA		3	CCC
5	EEE		4	DDD
3	CCC		5	EEE

Рис. 3.1. Сортировка записей

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

Рис. 3.2. Сортировка, использующая вспомогательную таблицу указателей

таблица указателей, так что вместо перемещения самих данных перемещаются эти указатели. Это называется сортировкой таблицы адресов.

Из-за взаимосвязи между сортировкой и поиском первым вопросом, который стоит, является вопрос о необходимости сортировки. Иногда при непосредственном поиске конкретного элемента в некотором множестве элементов затрачивается меньше работы, чем при сортировке данного множества и извлечении из него после сортировки необходимого элемента. С другой стороны, если в целях извлечения конкретных элементов требуется частое использование данного файла, то сортировка целесообразна. Она дает эффективность за счет того, что расходы (ресурсы, время) на следующие один за другим поиски могут существенно превысить расходы на выполнение разовой сортировки файла и последующего извлечения элементов из него. Программист должен принять соответствующее решение — выполнять сортировку или нет. Кроме того, программист помимо решения, что сортировать, должен выбрать как сортировать, т.е. метод сортировки. В настоящее время не существует метода сортировки, который бы во всем превосходил остальные.