Процессы обработки информации. Сортировка и поиск

Основные понятия сортировки

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

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

Чаще всего бывает необходимо сортировать записи по возрастанию или убыванию значений ключа, причем ключ может быть простым или составным.

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

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

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

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