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

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

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

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

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

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

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

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

15.Основные принципы сортировки

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

Если в поле ключа хранятся символьные данные, то в процессе сортировки сравниваются строки символов. В результате сортировки устанавливается лексикографический порядок следования записей. При сравнении символов сопоставляются двоичные коды их внутримашинного преставления. Сравнение строк символов производится в соответствии с определенными правилами. Пусть сравниваются две строки символов латинского алфавита: X₁X₂…X_m и Y₁Y₂…Y_n, где X_i и Y_i - символы, каждому из которых соответсвует определенный двоичный код. Первая строка будет считаться меньше второй строки в следующих случаях:

1. Если первая строка короче второй и все символы первой строки являются частью второй. Например, строка mask меньше строки masked

2. Если очередной символ первой строки меньше соответствующего символа второй строки. Например, строка read меньше строки record, строка readied меньше строки recon, строка data меньше строки file.

Различные приложения могут использовать в качестве ключа различные поля записей. В этом случае потребуется сортировка по нескольким ключам.

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

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

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

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

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