2.1 Понятие внутренней и внешней сортировки

Сортировка – это процесс упорядочения некоторого множества элементов, на котором определены отношения порядка >, <, , , =. Когда говорят о сортировке, подразумевают упорядочение множества элементов по возрастанию или убыванию. В случае наличия элементов с одинаковыми значениями, в упорядоченной последовательности они располагаются рядом друг с другом в любом порядке. Хотя иногда, бывает полезно сохранить первоначальный порядок элементов с одинаковыми значениями.

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

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

На практике редко требуется упорядочивать числа как таковые. Обычно надо сортировать записи (records), содержащие несколько полей, и располагать их в порядке, определяемом одним из полей. Например, в архиве отдела кадров для каждого сотрудника фирмы может храниться запись, содержащая различные поля (фамилия, имя, отчество, год рождения, адрес и т.п.), и в какой-то мо­мент может понадобиться упорядочить все записи по годам рождения. Поле, по которому проводится сортировка (год рождения в нашем примере), называется ключом (key), а остальные поля – дополнительными данными (satellite data).

По-сути, алгоритм сортирует ключи, но вместе с каждым ключом перемещаются (без изменения) дополнительные данные, с ним связанные. Если этих данных много, разумно перемещать не сами данные, а лишь указатель на них.

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