Сортировка массивов. Простые методы: сортировка вставками, выбором, обменом

Последовательности. Операции над последовательностями. Последовательный файл. Файл с прямым доступом. Стек, очередь, дек — способы реализации в программах и примеры практического использования.

Последовательности

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

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).

Сортировка массивов. Простые методы: сортировка вставками, выбором, обменом - student2.ru

Рисунок 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”).

Сортировка массивов. Простые методы: сортировка вставками, выбором, обменом - student2.ru

Рисунок 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).

Сортировка массивов. Простые методы: сортировка вставками, выбором, обменом - student2.ru

Рисунок 6 - Дек

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

Применение дека: например для построения деревьев.

Сортировка массивов. Простые методы: сортировка вставками, выбором, обменом.

Под сортировкой понимают процесс перестановки объектов данного множества в определенном порядке. Цель сортировки – ускорить последующий поиск элементов в отсортированном множестве.

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

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

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

Для определения эффективности алгоритма будем оценивать числа С – необходимых сравнений ключей и М – присваиваний элементов. Эти числа определяются некоторыми формулами от числа n сортируемых элементов. Хорошие алгоритмы сортировки требуют порядка Сортировка массивов. Простые методы: сортировка вставками, выбором, обменом - student2.ru сравнений.

Сортировка массивов

Введем некоторую терминологию: нам даны элементы – a1, a2, …, an. Сортировка означает перестановку этих элементов в таком порядке: ak1, ak2, …, akn, что при заданной функции упорядочения f справедливо отношение f(ak1)<=f(ak2)<=…<=f(akn).

Обычно функция упорядочения не вычисляется по какому-нибудь правилу, а содержится в каждом элементе в виде явной компоненты (поля). Ее значение называют ключом элемента. Для представления элемента ai будем использовать запись:

type item = record

key: integer;

{описание других компонент}

end;

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

Сортировка называется устойчивой, если записи с одинаковыми ключами остаются в прежнем порядке.

Наши рекомендации