Тема: «Исследование основных алгоритмов сортировок»
Сдам Сам

ПОЛЕЗНОЕ


КАТЕГОРИИ







Тема: «Исследование основных алгоритмов сортировок»





Цель работы – изучить принцип построения алгоритмов сортировок.

Теоретические сведения

Задача сортировки элементов массива

В общем случае сортировку следует понимать как процесс перегруппировки заданного множества объектов в некотором определённом порядке. Цель сортировки - облегчить поиск элементов в таком упорядоченном множестве.

Пусть надо упорядочить n элементов которые назовём записями. Каждая запись имеет свой ключ который и управляет процессом сортировки. Помимо ключа, запись может содержать дополнительную "сопутствующую информацию", которая не влияет на сортировку, но всегда остается в этой записи.

Задача сортировки - найти такую перестановку записей после которой ключи расположились бы в неубывающем порядке:

Основное требование к методам сортировки - экономное использование времени процессора и памяти. Хорошие алгоритмы затрачивают на сортировку n записей время порядка

Существующие методы сортировки обычно разбивают на три класса, в зависимости от лежащего в их основе приема:

а) сортировка выбором,

б) сортировка обменами,

в) сортировка включениями (вставками).

Рассмотрим основные алгоритмы сортировки на примере сортировки целочисленного массива.

Линейный выбор

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

1) Найти наименьший элемент, переслать его в рабочий массив и заменить его в исходном массиве величиной, которая больше любого реального элемента.

2) Повторить шаг (1). На этот раз будет выбран наименьший из оставшихся элементов.



3) Повторять шаг (1) до тех пор, пока не будут выбраны все n элементов.

Линейный выбор с обменом

Общая схема алгоритма следующая.

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

13.4 Стандартный обмен (метод "пузырька")

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

- после очередного прохода не сделано ни одного обмена;

- сделан проход для элементов

13.5 Челночная сортировка

Челночная сортировка, называемая также "сортировкой просеиванием" или "линейной вставкой с обменом" является наиболее эффективной из всех рассмотренных выше методов и отличается от сортировки обменом тем, что не сохраняет фиксированной последовательности сравнений.

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

Сортировка заканчивается, когда нисходящее сравнение выходит на границу массива.

Процесс челночной сортировки можно проследить на следующем примере:

Исходный массив: 2 7 9 5 4

Нисходящие сравнения: 2 7; 7 9; 9 5;

После перестановки: 2 7 5 9 4

Восходящие сравнения и обмен : 7 5 -> 5 7; 2 5 - конец восходящего сравнения; получен массив : 2 5 7 9 4

Нисходящие сравнения: 9 4

После перестановки: 2 5 7 4 9

Восходящие сравнения и обмен : 7 4 -> 4 7; 5 4 -> 4 5; 2 4 - конец восходящего сравнения; получен массив : 2 4 5 7 9 .

13.6 Сортировка Шелла

Все рассмотренные выше методы обмена были не столь эффективны при реализации на ЭВМ из-за сравнений и возможных обменов только соседних элементов. Лучших результатов следует ожидать от метода, в котором пересылки выполняются на большие расстояния. Один из таких методов предложил D.L.Shell.

Сортировка Шелла, называемая также "слиянием с обменом", является расширением челночной сортировки.

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

Таким образом, вначале сравниваются (и, если нужно, переставляются) далеко стоящие элементы, а на последнем проходе - соседние элементы.

Выигрыш получается за счет того, что на каждом этапе сортировки либо участвует сравнительно мало элементов, либо эти элементы уже довольно хорошо упорядочены, и требуется небольшое количество перестановок. Последний просмотр сортировки Шелла выполняется по тому же алгоритму, что и в челночной сортировке. Предыдущие просмотры подобны просмотрам челночной обработки, но в них сравниваются не соседние элементы, а элементы, отстоящие на заданное расстояние h. Большой шаг на начальных этапах сортировки позволяет уменьшить число вторичных сравнений на более поздних этапах.

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

a) 1, 4, 13, 40, 121, ... , где

б) 1, 3, 7, 15, 31, ... , где

13.7 Линейная вставка

Линейная (простая) вставка основана на последовательной вставке элементов в упорядоченный рабочий массив. Линейная вставка чаще всего используется тогда, когда процесс, внешний к данной сортировке, динамически вносит изменения в массив, все элементы которого известны и который все время должен быть упорядоченным.

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

3.8 Центрированная и двоичная вставки

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

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

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

Двоичная (бинарная) вставка в отличии от линейной использует для отыскания места вставки алгоритм двоичного (бинарного) поиска, т.е. при вставке j-го элемента он сравнивается вначале с элементом [j/2], затем, если он меньше, сравнивается с элементом [j/4], а если больше - с [j/2]+[j/4] и т.д. до тех пор, пока он не найдёт своё место. Все элементы рабочего массива, начиная с позиции вставки и ниже, сдвигаются на одну позицию вниз, освобождая место для j-го элемента.

13.9 Быстрая сортировка (метод Хоара)

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

Алгоритм быстрой сортировки, предложенный Хоаром, опять-таки использует тот факт, что для достижения наибольшей эффективности желательно производить обмены элементов на больших расстояниях.

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

Далее применим эту же процедуру к более коротким левому и правому подмножествам.

Таким образом, надо реализовать рекурсивный алгоритм, который сортирует элементы множества, начиная с элемента с индексом left и завершая элементом с индексом right. Условие окончания данного алгоритма - совпадение левой и правой границ подмножества (т.е. когда в подмножестве остается один элемент).

Точка деления массива может быть определена следующим образом. Вводятся два указателя i и j, причём вначале а Сравниваются i-й и j-й элементы и, если обмен не требуется, то j=j-1 и этот процесс повторяется. После первого обмена i увеличивается на единицу (i=i+1) и сравнения продолжаются с увеличением i до тех пор, пока не произойдёт ещё один обмен. Тогда опять уменьшим j и т.д. пока не станет i=j. К моменту, когда i=j элемент ai займёт свою окончательную позицию, так как слева от него не будет больших элементов, а справа - меньших. Таким образом, поставленная задача решена.

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

Пример 13.1. Упорядочить одномерный массив по возрастанию методом обмена. Фрагмент решения данной задачи представлено на рис.13.1а.

Пример 13.2. Рассмотрим задачу сортировки одномерного массива длины n методом обмена в порядке обменов.

При упорядочении можно использовать следующими правилами: числа сравниваются попарно: первое со вторым; второе с третьим; … , i-е с (i + 1); если меньшее стоит в паре на втором месте, то числа меняются местами. За один такой просмотр массива минимальное число перемещается по крайней мере на одно место вверх (вперед), а максимальное – в самый конец. Блок-схема этого алгоритма сортировки показана на рис.13.1б. При сортировке методом "пузырька" выполняется N-1 просмотров, на каждом i-м просмотре производится N-i сравнений. Общее количество С равно N* (N-1)/2,или O(N2).

Три вышеперечисленных метода часто называют прямыми. В них требуется порядка n*n сравнений.

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

а) б)

Рисунок 13.1 – Фрагмент алгоритма сортировки массива методом обменов и выбора

Индивидуальные задания

1) Создать алгоритм сортировки одномерного массива длиной N=50 по убыванию методом обмена.

2) Создать алгоритм сортировки одномерного массива длиной N=55 по возрастанию методом выбора.

3) Имеется одномерный массив длиной N=45. Создать алгоритм сортировки массива по убыванию методом выбора те элементы массива, которые являются четными.

4) Имеется одномерный массив длиной N=70. Создать алгоритм сортировки массива по возрастанию методом выбора те элементы массива, которые располагаются на нечетных позициях.

5) Создать алгоритм сортировки одномерного массива длиной N=29 по убыванию методом выбора.

6) Создать алгоритм сортировки одномерного массива длиной N=37 по возрастанию методом обмена.

7) Создать алгоритм сортировки одномерного массива по убыванию длиной N==44 методом выбора. После упорядочивания в каждой группе повторяющихся элементов оставить один, остальные – удалить.

8) Имеется одномерный массив длиной N=32. Создать алгоритм сортировки массива по возрастанию методом обмена те элементы массива, которые располагаются на нечетных позициях.

9) Имеется одномерный массив длиной N=32. Создать алгоритм сортировки массива по убыванию методом обмена те элементы массива, которые располагаются на нечетных позициях.

10) Имеется одномерный массив длиной N=25. Создать алгоритм так, чтобы упорядочить массив методом выбора, чтобы элементы, находящиеся на четных позициях располагались по возрастанию, а на нечетных – по убыванию.

11) Имеется одномерный массив длиной N=25. Создать алгоритм так, чтобы упорядочить массив методом выбора, чтобы элементы, находящиеся на четных позициях располагались по убыванию, а на нечетных – по возрастанию.

12) Имеется одномерный массив длиной N=25. Создать алгоритм так, чтобы упорядочить массив методом обмена, чтобы элементы, находящиеся на четных позициях располагались по убыванию, а на нечетных – по возрастанию.

Контрольные вопросы

1) Что понимается под определением сортировка?

2) Укажите основные виды сортировки и их особенности.

3) Приведите пример алгоритма сортировки методом выбора.

4) Приведите пример алгоритма сортировки методом обмена.

 

ЛАБОРАТОРНАЯ РАБОТА № 14









Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:


©2015- 2018 zdamsam.ru Размещенные материалы защищены законодательством РФ.