Сортировка массивов. Простые методы: сортировка вставками, выбором, обменом
Последовательности. Операции над последовательностями. Последовательный файл. Файл с прямым доступом. Стек, очередь, дек — способы реализации в программах и примеры практического использования.
Последовательности
Последовательность является элементарным классом данных. Последовательный тип можно описать следующим образом:
TYPE T = SEQUENCE OF T0;
Все элементы последовательности имеют один и тот же тип. Структура последовательности очень похожа на структуру массива. Существенное различие заключается в том, что у массива число элементов фиксируется в его описании, а у последовательности оно остается открытым, и предполагается, что в процессе работы программы оно может меняться. Хотя каждая последовательность в любой заданный момент времени имеет вполне определенную конечную длину, мощность последовательного типа считается бесконечной, поскольку на потенциальную длину переменных-последовательностей нет никаких ограничений.
Операции над последовательностями
1. Образование последовательности
Последовательность T, состоящую из элементов e1,…,en, представляют в виде T(e1,…,en). В частности, при n=0 последовательность T() называют пустой.
2. Выборка элементов последовательности
Если x – последовательность, то ее элементы можно записать следующим образом:
а) x[i] – i-й элемент; б) first(x) – первый элемент; в) last(x) – последний элемент.
3. Включение и исключение элементов последовательности
а) tail(x) – образование последовательности, исключая из x первый элемент;
б) initail(x); – образование последовательности, исключая из x последний элемент;
в) appendl(x,e) – образование последовательности с добавлением элемента e слева;
г) appendr(x,e) – образование последовательности с добавлением элемента e справа.
Последовательный файл
Последовательным файлом называется последовательность, для которой определены следующие операции: 1) образование пустой последовательности; 2) first(x) – получение первого элемента последовательности; 3) tail(x) – образование последовательности, исключая из x первый элемент; 4) appendr(x,e) – образование последовательности с добавлением элемента e справа.
Другими словами, последовательный файл представляет собой последовательность элементов, которая допускает выборку начального элемента последовательности и добавление элементов в ее конец. Такие последовательности реализуются на внешней запоминающей среде, например, ленте. Причем запись возможна только в одном направлении. Обработка файла реализуется путем введения файловой переменной f, а также дополнительной переменной типа T0 (T0 – тип компонентов файла), которая называется буферной переменной. Совокупность значений компонентов файла и положение буферной переменной определяют текущее состояние файла:
| f | e1 | e2 | … | ei | … | en-1 | en |
| fl | fr |
Рисунок 1 – текущее состояние файла
fl и fr служат для указания уже просмотренной и еще не просмотренной части файла. С их помощью текущее состояние файла можно задать в виде (fl, fr).
Файл с прямым доступом
Запоминающие устройства типа магнитного диска обычно содержат некоторое количество дорожек, каждая из которых представляет собой запоминающее устройство с последовательным доступом, но которое слишком мало для того, чтобы вместить целый файл или сегмент. Естественно, что указатель на начало такой мини последовательности служит маркером сегмента для адресации дорожек, с которых начинаются сегменты, и обозначением длины сегмента, может использоваться индексированная таблица. Такие файлы называются индексированными или файлами с прямым доступом. Системы, реализующие файлы с прямым доступом, позволяют выборочно изменять компоненты в середине файла.
Пример:
T1 = TEXT; { - последовательный доступ }
T2 = FILE OF <TYPE>; { - прямой доступ }
Стек
Стек – это последовательность, для которой определены следующие операции:
1) образование пустой последовательности;
2) first(x) – top; – получение первого элемента последовательности;
3) tail(x) – pop; – образование последовательности, исключая из x первый элемент;
4) appendl(x,e) – push; – образование последовательности с добавлением элемента e слева;
5) empty(x) – проверка на пустую последовательность.
Стек (рис. 2) – широко используемый тип данных, применяемый, например, для анализа языковых конструкций. Для стека добавление и извлечение элементов возможно только с одного конца последовательности, называющегося вершиной стека (слева). Таким образом, последний добавленный элемент извлекается из стека первым. Поэтому говорят, что стек – это структура с дисциплиной обслуживания «последним пришел – первым ушел» (LiFo).
Рисунок 2 - Стек
Стек в программах реализуют на основе вектора (массива) или односвязного линейного списка. В первом случае кроме массива нужно хранить указатель (индекс) вершины стека. Во втором варианте реализации добавление и удаление элемента осуществляются в начале списка.
Примеры
1. Рассмотрим математическое выражение с несколькими уровнями вложенных скобок. Необходимо удостовериться, что скобки расставлены правильно (следует проверить {[( = )]} ). Поэтому все открывающие скобки помещаем в стек, а когда встретится закрывающая, на верхушке стека должна открываться ей парная. После окончания проверки стек должен оказаться пустым.
2. Вычисление алгебраических выражений в постфиксной записи
После чтения очередного операнда он записывается в стек. Когда читается операция, то из стека извлекаются два последних операнда и к ним применяется операция. Результат помещается опять в стек.
ПОКА входная строка не пуста
Symb := следующий символ;
ЕСЛИ Symb = операнд
ТО appendl(x, Symb)
ИНАЧЕ SecondOper := tail(x);
FirstOper := tail(x);
Value := FirstOper (Symb) SecondOper;
appendl(x, Value);
Применение стека: стек применяется практически во всех алгоритмах, так как он является основой реализации видимости переменных - глобальных и локальных, кроме этого стек применяется в случаях, когда необходимо организовать прерывания вызовов и возвратов.
Очередь
Очередь – это последовательность, для которой определены следующие операции:
1) образование пустой последовательности;
2) last(x) – получение последнего элемента последовательности;
3) initail(x) – образование последовательности, исключая из x последний элемент;
4) appendl(x,e) – образование последовательности с добавлением элемента e слева;
5) empty(x) – проверка на пустую последовательность.
Часто очередь (рис. 3) называют матрицей ожидания. Добавление в очередь осуществляется с левого конца, выборка – с правого. Очередь – это структура с дисциплиной обслуживания «первым пришел – первым ушел» (FiFo – “First input First output”).
Рисунок 3 - Очередь
Часто очередь реализуют на базе вектора, т.е. одномерного массива. Но в силу его ограниченности рано или поздно может наступить такое состояние, что дальнейшее наращивание невозможно, хотя в массиве еще много свободного места. Поэтому очередь реализуется на базе циклического вектора, который позволяет избежать массовых операций, зависящих от количества элементов в очереди. Использование циклического вектора означает, что при достижении конца массива данные в очередь начинают заноситься в освобожденное в его начале место. Например, если в очереди находятся числа 1, 2, 3, 4, 5, 6, 7, а в массиве зарезервировано место для десяти чисел, то хранение очереди в массиве может быть следующим:
| <пусто> | <пусто> | <пусто> | |||||||
| Правый конец очереди | Левый конец очереди |
Рисунок 4 – хранение очереди в массиве для десяти чисел
Кроме того, очередь можно реализовать на основе односвязного линейного списка. При этом нужно иметь два указателя на начало и конец списка, добавление элемента осуществлять в конец списка, а удаление – из его начала.
Пример. Нахождение одного из кратчайших путей в лабиринте.
1. Помечается исходная клетка значением 1.
2. Каждая новая помеченная клетка помещается в очередь.
3. Из очереди производится выборка клетки, все ее не помеченные соседки помечаются числом, большим на единицу.
4. Продолжаем шаги 2, 3 пока очередь не будет пуста или не будет достигнута клетка назначения.
5. Если очередь пуста, а последняя выбранная из очереди клетка – не клетка назначения, то пути не существует, иначе путь строится последовательным соединением клеток, начиная с клетки назначения с убыванием значения предыдущей клетки на единицу.
Применение очереди:
Примером может служить организация событий в Windows. Когда пользователь оказывает какое-то действие на приложение, то в приложении не вызывается соответствующая процедура (ведь в этот момент приложение может совершать другие действия), а ему присылается сообщение, содержащее информацию о совершенном действии, это сообщение ставится в очередь, и только когда будут обработаны сообщения, пришедшие ранее, приложение выполнит необходимое действие.
Клавиатурный буфер BIOS организован в виде кольцевого массива, обычно длиной в 16 машинных слов, и двух указателей: на следующий элемент в нём и на первый незанятый элемент. Таким образом, очередь применяется для многопроцессорных обработок.
Дек
Дек– это последовательность, для которой определены следующие операции:
1) образование пустой последовательности;
2) appendl(x,e) – образование последовательности с добавлением элемента e слева;
3) appendr(x,e) – образование последовательности с добавлением элемента e справа;
4) tail(x) – образование последовательности, исключая из x первый элемент;
5) initail(x) – образование последовательности, исключая из x последний элемент;
6) first(x) – получение первого элемента последовательности;
7) last(x) – получение последнего элемента последовательности;
8) empty(x) – проверка на пустую последовательность.
Дек – это «гибрид» очереди и стека, в нем очередь движется как вправо, так и влево (рис. 6). Поэтому дек еще называют двусторонней очередью (Double Ended Queue).
Рисунок 6 - Дек
В программах дек реализуют либо на основе циклического вектора, либо на основе двусвязного линейного списка.
Применение дека: например для построения деревьев.
Сортировка массивов. Простые методы: сортировка вставками, выбором, обменом.
Под сортировкой понимают процесс перестановки объектов данного множества в определенном порядке. Цель сортировки – ускорить последующий поиск элементов в отсортированном множестве.
Методы сортировки обычно разделяют на две категории: сортировка массивов и сортировка файлов. Эти два класса часто называют внутренней и внешней сортировкой, так как массивы располагаются во «внутренней» (оперативной) памяти ЭВМ (для этой памяти характерен быстрый произвольный доступ), а файлы хранятся в более медленной, но более вместительной «внешней» памяти, т.е. на запоминающем устройстве с механическим передвижением (дисках, лентах).
Основные критерии эффективности алгоритмов сортировки: быстродействие; экономия памяти; сокращение времени, затрачиваемого программистом, на реализацию алгоритма.
Поэтому в зависимости от количества элементов множества, их упорядоченности, частоты применения сортировки и других факторов следует использовать различные алгоритмы сортировки.
Для определения эффективности алгоритма будем оценивать числа С – необходимых сравнений ключей и М – присваиваний элементов. Эти числа определяются некоторыми формулами от числа n сортируемых элементов. Хорошие алгоритмы сортировки требуют порядка 
сравнений.
Сортировка массивов
Введем некоторую терминологию: нам даны элементы – a1, a2, …, an. Сортировка означает перестановку этих элементов в таком порядке: ak1, ak2, …, akn, что при заданной функции упорядочения f справедливо отношение f(ak1)<=f(ak2)<=…<=f(akn).
Обычно функция упорядочения не вычисляется по какому-нибудь правилу, а содержится в каждом элементе в виде явной компоненты (поля). Ее значение называют ключом элемента. Для представления элемента ai будем использовать запись:
type item = record
key: integer;
{описание других компонент}
end;
Прочие компоненты – это все существенные данные об элементе, поле key служит лишь для идентификации элементов. Однако, когда мы говорим об алгоритмах сортировки, ключ – единственная существенная компонента, и нет необходимости выделять все остальные.
Сортировка называется устойчивой, если записи с одинаковыми ключами остаются в прежнем порядке.