Сортировка.

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

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

Для понимания процессов обработки информации необходимы следующие категории данных.

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

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

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

При решении подавляющего большинства задач применяются общие, повторяющиеся процессы обработки информации. Широко распространенными являются: упорядочивание массивов, поиск информации и др.

Сортировка.

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

Сортировка стала важным предметом вычислительной математики в основном потому, что она занимает до 25% всего времени вычислений. Сортировка применяется при трансляции программ, когда составляются таблицы символов; она также является важным средством для ускорения работы практически любого алгоритма, в котором часто нужно обращаться к определенным элементам.

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

Пусть надо упорядочить N записей a₁, a₂, …, a_N. Совокупность N записей назовем файлом. Каждая запись a_i имеет ключ К_i, который управляет процессом сортировки. Отношение порядка “< ” на множестве ключей необходимо вводить таким образом, чтобы для любых трех значений ключей а, b, c выполнялись следующие условия:

1. Справедливо одно и только лишь одно из соотношений a< b, a=b, b< a (закон трихотомии).

2. Если a< b и b< с, то a< с (закон транзитивности).

Эти два свойства определяют математическое понятие линейного упорядочения. Под задачей сортировки следует понимать нахождение такой перестановки записей a₁, a₂, …, a_N, после которой ключи расположились бы в неубывающем порядке: К₁£ К₂£ …£ К_N.

Сортировка называется устойчивой, если в результате сортировки записи с одинаковыми ключами остаются в прежнем порядке, т.е. a_i £ a_j, если К_i = К_j и i< j.

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

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

Организация сортировки существенно зависит от количества элементов в массивах и от того, какая память используется для хранения и преобразования массивов в процессе сортировки. Будем условно называть “малыми” такие массивы, объем которых не превосходит емкость оперативной памяти (ОЗУ). Сортировку таких массивов внутри ОЗУ называют внутренней сортировкой.

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

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

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

Таблица 1.1.

где C – количество необходимых сравнений ключей;

М – количество пересылок элементов;

Min, Max, Средн. – значения для всех n! перестановок элементов.

Эти формулы дают лишь приблизительную оценку эффективности как функции от n. Они допускают классификацию алгоритмов сортировки на простые (n²) и усовершенствованные, или “логарифмические” (n log n).

Как правило, для выполнения внутренней сортировки помимо памяти, занятой программой сортировки и сортируемым массивом, требуется дополнительный объем памяти – резерв памяти. Его объем, в зависимости от методов сортировки, колеблется в широких пределах и существенно влияет на объем оперативной памяти, используемой для внутренней сортировки.

Таким образом, критерий быстродействия для оценки внутренней сортировки может быть сведен к следующим показателям: необходимое число сравнений и обращений к памяти; необходимый объем памяти.

С другой стороны, необходимо иметь в виду, что подсчет числа сравнений – не единственный способ измерить эффективность метода сортировки.

Введем значения: N (записей) – емкость массива, подлежащего внутренней сортировке; S (записей) – емкость памяти, требуемой для сортировки. DS = S – N - резерв памяти; С – среднее количество попарных сравнений, необходимых для сортировки массива; D – среднее количество обращений к памяти (чтение или запись элемента массива). Величина С зависит от метода сортировки и при рациональном выборе достигает некоторого минимума С_min. Для минимального числа сравнений, достаточного для сортировки N элементов, имеется следующее соотношение:

(1.1)

где [x] – ближайшее целое, большее или равное х.

Соотношение (1.1) часто называют “теоретико-информационной нижней оценкой”. По формуле Стирлинга

(1.2)

где О(1) – обозначение остатка.

При выполнении попарных сравнений, каждое из которых имеет два исхода, необходимое число сравнений для полного упорядочения совокупности из N случайных чисел с достаточной для практика точности можно считать равным:

(1.3)

Идеальным можно считать такой метод сортировки, при котором

(1.4)

Для оценки эффективности конкретных алгоритмов сортировок проводятся специальные исследования (см. список литературы).

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

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

Выделим следующие шесть основных методов внутренней сортировки:

1. Метод вставки. Элементы просматриваются по одному, на i-том этапе i-тый элемент помещается на подходящее место между (i-1) уже отсортированных элементов.

2. Обменная сортировка. Если два элемента расположены не по порядку, то они меняются местами. Этот процесс повторяется до тех пор, пока элементы не будут упорядочены.

3. Метод выбора. На i-том этапе из неотсортированных элементов выбирается i-тый наибольший (или наименьший) элемент и помещается на соответствующее место.

4. Распределение. Элементы распределяются по группам, и содержимое групп затем объединяются таким образом, чтобы частично отсортировать все множество элементов. Процесс повторяется до тех пор, пока множество не будет отсортировано полностью.

5. Сортировка подсчетом. Каждый элемент сравнивается со всеми остальными; окончательное положение элемента определяется подсчетом числа меньших ключей.

6. Слияние. Множество элементов разбивается на группы, которые сортируются и затем объединяются в одну группу.

Многие алгоритмы сортировки могут быть отнесены одновременно к нескольким из основных методов, т.е. они являются гибридными.

Поиск.

Одним из наиболее важных и широко распространенных процессов обработки информации является поиск. Задача поиска в информационном массиве (ИМ) состоит из нахождения элемента, который удовлетворяет некоторому заданному условию.

Предположим, что в памяти хранится ИМ из N элементов. Если в качестве элементов выступают записи, тогда имеем файл из N записей. Каждая запись содержит поле ключа, причем все N значений ключей различны, т.е. записи определяются ключом однозначно. В алгоритмах поиска присутствует так называемый аргумент поиска z, который является ключом искомой записи. Задача поиска состоит в отыскании записи, имеющей ключ Z.

Поиск может осуществляться по первичному ключу, который однозначно определяет запись в файле. Но иногда необходимо вести поиск, основываясь не на первичных ключах, а на значениях других полей записи, которые называются атрибутами или вторичными ключами записи. Выборка по вторичным ключам соответствует вторичным методам доступа и допускает одинаковые значения вторичных ключей для нескольких записей, т.е. из файла выбираются записи с одинаковыми значениями атрибутов. Например, из файла СЛУЖАЩИЕ выбираются служащие одного года рождения.

Существует две возможности окончания поиска: поиск удачен, т.е. положение записи, содержащей z, определено, или поиск неудачен, т.е. аргумент z не может быть найден ни в одной из записей.

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

К первой группе следует отнести:

I. Метод последовательного поиска. Элементы ИМ просматриваются последовательно в соответствии с отношением следования, определенном на данном множестве элементов.

II. Метод бинарного поиска. Аргумент поиска (ключ) сравнивается со средним элементом из упорядоченной последовательности. Выделяется один интервал из двух, в котором должен содержаться искомый элемент. Для выбранного интервала изложенный способ повторяется.

Ко второй группе следует отнести:

I. Метод позиционной адресации, основанный на непосредственной выборке по номеру, определяемому функцией преобразования ключей. Эта функция реализует взаимооднозначное соответствие 1: 1 между множеством ключей и множеством адресов записей.

II. Метод вычисления адреса, предполагающий преобразование ключа элемента в адрес или номер в памяти с помощью хеш-функции, которая реализует соответствие типа М: 1 между множеством ключей и множеством адресов записей.

Выбор стратегии поиска существенно зависит от структуры данных, способа их организации и условий, по которым осуществляется выбор элементов.

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

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