ОСНОВНЫЕ ПОНЯТИЯ И ПРИНЦИПЫ СОРТИРОВКИ

Под сортировкой обычно понимают процесс перестановки объектов данного множества в определенном порядке. Цель сортировки — облегчить последующий поиск элементов в от­сортированном множестве.

В этом смысле элементы сорти­ровки присутствуют почти во всех задачах. Упорядоченные объекты содержатся в телефонных книгах, в ведомостях по­доходных налогов, в оглавлениях, в библиотеках, в словарях, на складах, да и почти всюду, где их нужно разыскивать. Даже маленьких детей приучают приводить вещи «в поря­док», и они сталкиваются с некоторым видом сортировки задолго до того, как узнают что-либо об арифметике.

Сортировки обычно разделяют на две категории: сортировка массивов и сортировка последовательных файлов. Их часто называют внутренней и внешней сортировкой, так, как массивы располагаются во внутренней памяти ЭВМ, а файлы хранятся в более медленной, но более вместительной «внешней» памяти, т.е. на запоминающих устройствах с механическим передвижением (дисках, лентах).

Единицей данных, обрабатываемых информационными системами, является запись, состоящая из ряда информационных полей. Ключом может быть содержимое одного поля записи (ключевого поля) или совокупности определенных полей. В последнем случае ключ называется составным. Запись может состоять из единственного поля, которое в дан­ном случае и будет являться ключевым. В результате упорядочивания записи располагаются по возрастанию или убыванию значений ключей. Так, записи, содержащие сведения о студентах факультета, могут быть упорядочены по номерам их зачетных книжек. Процесс упорядочивания записей по возрастанию или убыванию значений ключа называется сорти­ровкой.

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

число операций сравнения, выполняемых в процессе сортировки С и среднее число перестановок или обменов элементов. Эффективность сортировки определяется как частное от деления среднего числа срав­нений на число элементов массива.

Не нашли, что искали? Воспользуйтесь поиском: