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

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

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

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

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

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

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

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

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

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

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

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

Литература

1. 002.05 (021) Т 761 И.П.Трофимова. Системы обработки и хранения информации. М. "Высшая школа", 1989

2. 1539 Линейные структуры данных. Метод. указания к лаб. работам.

Вопросы для самостоятельно проработки ( указаныпараграфыучебника )

Сортировка методом выбора – п. 11.2.

Сортировка методом обмена – п. 11.2.

Сортировка методом вставок – п.11.2.

Сортировка методом подсчета (в отсутствии и при наличии одинаковых ключей) – п. 11.2, методичка.

Сортировка методом Шелла – п.11.2.

Внешняя сортировка – п.11.3.