Курсовая работа: Алгоритмы сортировки, поиска кратчайшего пути в графе и поиска покрытия, близкого к кратчайшему

1) (Ymod 4) + 1 =(509 mod 4) + 1=1 + 1= 2; Алгоритм покрытия: построение одного кратчайшего покрытия.

2) (Ymod 6) + 1 =(509 mod 6) + 1 = 5 + 1=6; Алгоритм на графах: поиск кратчайшего пути.

3) (Ymod 5) + 1 =(509 mod 5) +1 =4 + 1 = 5; Алгоритм сортировки: сортировка-шейкер.

2 АЛГОРИТМ СОРТИРОВКИ: СОРТИРОВКА ШЕЙКЕР

2.1 Математическое описание задачи

Сортировка – это перестановка элементов некоторого множества в заданном порядке при некоторой упорядочивающей функцию.

Сортировка используется для облегчения поиска элемента в таком отсортированном множестве.

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

2.2 Словесное описание алгоритма и его работы

Сортировка Шейкер является усовершенствованной сортировкой методом пузырька. Идея метода: шаг сортировки состоит в проходе снизу вверх по массиву. По пути просматриваются пары соседних элементов. Если элементы некоторой пары находятся в неправильном порядке, то меняем их местами.(см. Таб. 1)

Таблица 1

i=1	2	3	4	5	6	7	8
44	06	06	06	06	06	06	06
55	44	12	12	12	12	12	12
12	55	44	18	18	18	18	18
42	12	55	44	42	42	42	42
94	42	18	55	44	44	44	44
18	94	42	42	55	55	55	55
06	18	94	94	67	67	67	67
67	67	67	67	94	94	94	94

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

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

Тем не менее, у него есть громадный плюс: он прост и его можно по-всякому улучшать. Чем мы сейчас и займемся. Во-первых, рассмотрим ситуацию, когда на каком-либо из проходов не произошло ни одного обмена. Что это значит ? Это значит, что все пары расположены в правильном порядке, так что массив уже отсортирован. И продолжать процесс не имеет смысла(особенно, если массив был отсортирован с самого начала !). Итак, первое улучшение алгоритма заключается в запоминании, производился ли на данном проходе какой-либо обмен. Если нет - алгоритм заканчивает работу. Процесс улучшения можно продолжить, если запоминать не только сам факт обмена, но и индекс последнего обмена k. Действительно: все пары соседих элементов с индексами, меньшими k, уже расположены в нужном порядке. Дальнейшие проходы можно заканчивать на индексе k, вместо того чтобы двигаться до установленной заранее верхней границы i.

Качественно другое улучшение алгоритма можно получить из следующего наблюдения. Хотя легкий пузырек снизу поднимется наверх за один проход, тяжелые пузырьки опускаются со минимальной скоростью: один шаг за итерацию. Так что массив 2 3 4 5 6 1 будет отсортирован за 1 проход, а сортировка последовательности 6 1 2 3 4 5 потребует 5 проходов.

Чтобы избежать подобного эффекта, можно менять направление следующих один за другим проходов. Получившийся алгоритм называют "шейкер-сортировкой ". Далее проведена программа на языке С++, реализующая сортировку Шейкер.

template<class T>void shakerSort(T a[], long size) {longj, k = size-1;long lb=1, ub = size-1; // ??????? ????????????????? ????? ???????Tx; do {// ?????? ????? ?????for( j=ub; j>0; j-- ) {if ( a[j-1] > a[j] ) {x=a[j-1]; a[j-1]=a[j]; a[j]=x;k=j;}} lb = k+1; // ?????? ?????? ????for (j=1; j<=ub; j++) {if ( a[j-1] > a[j] ) {x=a[j-1]; a[j-1]=a[j]; a[j]=x;k=j;}} ub = k-1;} while ( lb < ub );}

Насколько описанные изменения повлияли на эффективность метода ? Среднее количество сравнений, хоть и уменьшилось, но остается O(n² ), в то время как число обменов не поменялось вообще никак. Среднее(оно же худшее) количество операций остается квадратичным, количество излишних двойных проверок сократилось.

Дополнительная память, очевидно, не требуется. Поведение усовершенствованного (но не начального) метода довольно естественное, почти отсортированный массив будет отсортирован намного быстрее случайного. Сортировка пузырьком устойчива, однако шейкер-сортировка утрачивает это качество.

На практике метод пузырька, даже с улучшениями, работает, увы, слишком медленно. А потому - почти не применяется.

2.3 Описание схемы алгоритма

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

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

n – количество элементов массива;

A – сортируемый массив;

j – переменная;

x – i-й ключ (переносимый элемент);

r – номер последнего обмена при просмотре входной последовательности слева-направо.

l - номер последнего обмена при просмотре входной последовательности справа -

налево.

Все переменные целого типа.

Описание схемы алгоритма.Блок-схема данного алгоритма изображена на рис. 1 в Приложении.

Алгоритм работает следующим образом. Сначала вводятся исходные данные: длина массива и его элементы (блок 1, 2) , затем организуется цикл по всей длине массива, во время которого (блоки 3 -7) и проводится сравнение элементов а[j-1]>a[j] и их обмен при проходе справа-налево . Номер последнего обмена l запоминается. Далее организуется цикл, в котором проводится проверка условия а[j-1]>a[j] при проходе массива слева-направо (блоки 8 - 12).

2.4 Контрольный пример

Рассмотрим пример работы алгоритма сортировки Шейкер.

Задан массивA, состоящий из 8 элементов: 44, 55, 12, 42, 94, 18, 6, 67.