СОРТИРОВКА И ПОИСК
Сортировка
Сортировкой называется процесс упорядочения информации по определенному критерию, например, по возрастанию или по убыванию ключей, по алфавиту и т.п.
Рассмотрим различные методы сортировки:
A. Сортировка выбором
B. Сортировки включением.
C. Сортировка обменом
D. Сортировка слиянием
E. Внешняя сортировка
При построении двоичного дерева по набору признаков мы также использовали алгоритм сортировки (упорядочение дерева по набору признаков - влево, вправо и т.п.).
Рассмотрим несколько алгоритмов сортировки. Прежде всего, отметим, что все описанные алгоритмы сортировки называются алгоритмами внутренней сортировки, так как предполагается, что все упорядочение осуществляется в оперативной памяти. Одно из основных требований к методам сортировки это экономия памяти.
При экономии памяти не рекомендуется формировать вспомогательные массивы, которые будут использовать дополнительную память.
Второе требование к методам сортировки – это повышение быстродействия алгоритма.
А. Сортировка выбором
Дано: Множество элементов М={M[1], M[2], …, M[n]}.
Необходимо: Упорядочить это множество по убыванию (по возрастанию действия будут выполняться по аналогичной схеме).
Схема сортировки следующая:
1. Пусть i – номер элемента в массиве М. На первом шаге i=1.
2. Найти максимальный элемент в множестве М[i], M[i+1], …, M[n].
3. Поменять его местами с первым элементом М[i].
4. Увеличить i на единицу (то есть, i:=i+1).
5. Выполнять шаги 2-4 пор тех пор, пока i не станет равно n; в этом случае, на последнем месте будет находиться минимальный элемент.
Оценим данный алгоритм:
Шаги 1-2 будут повторяться: Если n – количество элементов в последовательности.
Сначала (n-1), потом (n-2), потом (n-3), … 2, 1 раз. То есть мы имем:
n-1+n-2+n-3+… +2+1=n(n-1)/2=(n2-n)/2
То есть оценка этого алгоритма сортировки == О((n2-n)/2).
B. Сортировка включением
Дано: Последовательность элементов М={M[1], M[2], …, M[n]}. Предположим, что она уже упорядочена. Включение в последовательность М нового элемента – это нахождение места размещения его в М.
Необходимо: Упорядочить эту последовательность по убыванию (по возрастанию действия будут выполняться по аналогичной схеме).
Схема сортировки следующая:
1. Пусть n – количество элементов в последовательности М.
2. Сначала n=0 (то есть последовательность М – пуста). i - индекс элементов в М, используется для нумерации элементов последовательности.
3. Взять m – добавляемый элемент.
4. Если n=0, то
4.1. просто поместить m в М на первое место; то есть M[1]:=m;
4.2. при этом количество элементов в М станет равно 1: n:=n+1 (=1).
5. Иначе (то есть, если n>0)
5.1. i:=1;
5.2. если m>M[i], то
5.2.1. сдвинуть элементы M[i], M[i+1], …, M[n] вправо, а на место M[i] записать элемент m;
5.2.2. n:=n+1 (то есть количество элементов увеличивается на 1);
5.2.3. перейти на выполнение шага 3;
5.3. иначе:
5.3.1. i:=i+1 (то есть перейти к следующему элементу);
5.3.2. если i>n, то:
5.3.2.1. записать m на место M[n+1];
5.3.2.2. n:=n+1 (то есть количество элементов увеличивается на 1);
5.3.2.3. перейти на выполнение шага 3.
5.3.3. иначе повторить шаги 5.2-5.3.
6. Выполнять шаги 2-4 пор тех пор, пока поступают новые элементы, добавляемые в последовательность М.
Оценка алгоритма сортировки включением:
Данный алгоритм сортировки требует О((n2-n)/2) операций сравнения.
Если здесь использовать метод двоичного поиска то сложность алгоритма будет О(n*Log2n) операций сравнения.
C. Сортировка обменом
Эту сортировку иногда называют сортировкой «Пузырьком».
Дано: Последовательность элементов М={M[1], M[2], …, M[n]}.
Необходимо: Упорядочить эту последовательность по убыванию (по возрастанию действия будут выполняться по аналогичной схеме).
Схема сортировки будет следующая:
1. Сравнить два первых элемента А и В, если А<В, то поменять их местами.
2. Сравнить второй и третий элементы В и С. Если В меньше С, то поменять их местами.
3. Продолжить процесс сравнения до конца множества (массива). При этом минимальный элемент окажется на последнем месте.
4. Выполнить шаги 1-3, начиная от первого элемента до найденного на предыдущем шаге минимального. Процесс закончен, как только мы выполнили шаг 4 -- (n-1) раз.
Упражнение 4.
Оцените этот алгоритм самостоятельно.
D. Сортировка слиянием
Дана последовательность элементов М. Для простоты снова предположим, что мощность этого множества = n.
Тогда схема этого алгоритма сортировки будет следующая:
1. Разбить множество М на два равных М1 и М2.
2. Упорядочить каждое из этих множеств (но по одному признаку, то есть или по возрастанию, или по убыванию).
3. «Слить» эти множества в одно.
Заметим, что общее время работы такого алгоритма = O(n*log2n).
E. Внешняя сортировка
Сортировка информации, хранящейся в файлах на дисках, называется внешней. Многие способы внутренней сортировки, описанные выше, без изменения применимы и к данным, расположенным во внешней памяти.
Например, построение двоичного дерева по набору признаков, хранящихся в файле. (Здесь можно использовать любой из изученных файлов – текстовый, типизированный, нетипизированный).
Упражнение.
Записать все рассмотренные выше алгоритмы сортировок, учитывая тот факт, что исходная информация хранится в одном файле. Тип и структуру файла установить самостоятельно.
Интересным является алгоритм внешней сортировки, при котором, информация хранится в двух или более файлах. В этом случае лучше использовать один из алгоритмов сортировки слиянием. В этом случае, каждый из файлов должен быть упорядочен. Причем упорядочение всех файлов, участвующих в сортировке должно быть по одному признаку (по возрастанию, или убыванию).
Поиск
Поиском называется процесс нахождения элемента в множестве данных.
Поиск является наиболее эффективным, если исходное множество данных отсортировано, то есть упорядочено по данному ключу.
Рассмотрим сложность алгоритма поиска в неупорядоченном множестве.
Пусть дано множество М={а1, а2, …, аn}. Данное множество произвольное, то есть неупорядоченное. Тогда алгоритм поиска элемента А в множестве М будет стандартным, то есть, необходимо сравнивать каждый элемент М[i] с требуемым элементом А (или проверять его, удовлетворяет ли данный элемент требуемому критерию – например, является ли он наименьшим) до тех пор, пока не будет найден исходный элемент А или пока множество М не будет полностью рассмотрено, а элемент А, удовлетворяющий требуемому критерию так и не найден. Тогда сложность по времени алгоритма поиска элемента А в данном множестве будет О (n), где n – мощность множества М.
Для ускорения алгоритма поиска обычно используют различные стратегии. Одна из них получила название «Разделяй и властвуй». В этой стратегии, исходное множество разбивается на два (М1 и М») по [n/2] в одном множестве и (n-[n/2]) элементов в множестве. Если использовать рекурсивную процедуру, то можно более эффективный по времени алгоритм. Рассмотрим данную стратегию на примере следующей задачи.
Пример
Дано множество М={а1, а2, …, аn}. Для простоты предположим, что мощность М есть степень числа 2. Необходимо найти в нем наименьший и наибольший элемент. Очевидный путь нахождения этих элементов, это поиск каждого их них по отдельности.
Например, процедура нахождения максимального элемента
Max:=M[1];
Для i:=1 до n Выполнить
Если M[i]>Max то Max:=M[i]
Будет выполняться за (n-1) сравнений.
Для нахождения наименьшего элемента из остальных (n-1) элементов необходимо выполнить как минимум (n-2) сравнения.
Таким образом, для нахождения максимального и минимального элемента при n>=2 требуется (2n-2) сравнений.
Если же использовать стратегию «Разделяй и властвуй», то алгоритм решения этой задачи можно записать следующим образом:
К последовательности М применяется рекурсивная процедура MAXMIN. Она имеет два входных аргумента – вышеописанное множество М и его мощность. Эта процедура формирует пару (Max, Min).
Заметим, что сравнение элементов множества М происходит только на шаге 3 (сравниваются 2 элемента – множество состоит только их двух элементов) и на шаге 7 (где сравниваются max1 и max2, min1 и min2). Индукцией можно доказать, что общее число сравнений будет Т(n)=(3/2)*n-2. Сравните с (2n-2)!
Эффективность хорошо видна при достаточно большом n.
Например, пусть n=100 000 000. Тогда, по первому алгоритму мы имеем количество сравнений = 199 999 998, по второму = 149 999 998. Разница= 50 000 000 При n=100 000 000 000. Тогда, по первому алгоритму мы имеем количество сравнений = 199 999 999 998, по второму = 149 999 999 998. Разница=50 000 000 000.
Заметим, что в данном случае мы имели дело с неупорядоченным множеством.
Упражнение.
1. Написать процедуру MinMax на Object Pascal.
2. Написать главный модуль, осуществляющий ввод информации в массив (множество), вызов этой процедуры и печать результата (то есть, напечатать, принадлежит ли элемент множеству, и если “да”, то порядковый номер этого элемента в множестве.
Эту же стратегию можно применить и при поиске элемента А в упорядоченном множестве М.
Пример
Необходимо определить, принадлежит ли А множеству М, где индексы множества принадлежат диапазону [d1,d2], и найти порядковый номер этого элемента А.
Такой алгоритм обычно называют алгоритмом “ двоичного поиска ”, или метод деления множества пополам.
Упражнение.
1. Найти оценку приведенного в пример 2 алгоритма. Сравнить эту оценку с стандартным алгоритмом поиска (полным перебором). (логарифмы!)
2. Написать главный модуль, осуществляющий ввод информации в массив (множество), вызов этой процедуры и печать результата (то есть, напечатать, принадлежит ли элемент множеству, и если “да”, то порядковый номер этого элемента в множестве.
В примере необходимым требованием является упорядочение множества элементов.
Заметим, что задача MinMax решается очень просто, если множество (массив) упорядочено (просто берутся первый и последний элементы массива).
Упражнение. (Выполнить хотя бы приближенно, по аналогии с описанным выше)
1. Найти оценки процесса поиска элемента в двоичном несбалансированном дереве.
2. Найти оценки процесса поиска элемента в двоичном сбалансированном дереве. Сравнить с оценкой поиска в несбалансированном дереве.
Примеры сортировок
Приведем примеры работы алгоритмов сортировок
A. Сортировка выбором
B. Сортировки включением.
C. Сортировка обменом
D. Сортировка слиянием
A. Пример сортировки выбором
Дано: Множество элементов М={1, 11, 2, 12, 3, 14, 4, 15}; n=8.
Выполняем сортировку выбором (по убыванию) по вышеописанной схеме:
| № шага | Значение i | Множество М | Комментарий |
| 1, 11, 2, 12, 3, 14, 4, 15 | М[1] = 1 | ||
| 1, 11, 2, 12, 3, 14, 4, 15 | Max=M[8]=15; | ||
| 15, 11, 2, 12, 3, 14, 4, 1 | меняем M[1] и M[8] местами | ||
| 15, 11, 2, 12, 3, 14, 4, 1 | М[2] = 11 | ||
| 15, 11, 2, 12, 3, 14, 4, 1 | Max=M[6]=14; | ||
| 15, 14, 2, 12, 3, 11, 4, 1 | меняем M[2] и M[6] местами | ||
| 15, 14, 2, 12, 3, 11, 4, 1 | М[3] = 2 | ||
| 15, 14, 2, 12, 3, 11, 4, 1 | Max=M[4]=12; | ||
| 15, 14, 12, 2, 3, 11, 4, 1 | меняем M[3] и M[4] местами | ||
| 15, 14, 12, 2, 3, 11, 4, 1 | М[4] = 2 | ||
| 15, 14, 12, 2, 3, 11, 4, 1 | Max=M[6]=111; | ||
| 15, 14, 12, 11, 3, 2, 4, 1 | меняем M[4] и M[6] местами | ||
| 15, 14, 12, 11, 3, 2, 4, 1 | М[5] = 3 | ||
| 15, 14, 12, 11, 3, 2, 4, 1 | Max=M[7]=4; | ||
| 15, 14, 12, 11, 4, 2, 3, 1 | меняем M[5] и M[7] местами | ||
| 15, 14, 12, 11, 4, 2, 3, 1 | М[6] = 2 | ||
| 15, 14, 12, 11, 4, 2, 3, 1 | Max=M[7]=3; | ||
| 15, 14, 12, 11, 4, 3, 2, 1 | меняем M[6] и M[7] местами | ||
| 15, 14, 12, 11, 4, 3, 2, 1 | М[7] = 2 | ||
| 15, 14, 12, 11, 4, 3, 2, 1 | Max=M[7]=2; | ||
| 15, 14, 12, 11, 4, 3, 2, 1 | обмена нет | ||
| Последовательность упорядочена |