Метод прямого обмена (пузырьковая сортировка)
Метод основывается на сравнении и последующем перестановке пары соседних элементов в местах, где нарушен порядок сортировки. На первом шаге сравниваются ключи 
и 
. Если порядок их сортировки нарушен, элементы 
и 
меняются местами. На следующем шаге проверяются элементамы 
и 
и т. д. При последовательном повторении операции запись с самым большим значением ключа будет передвигаться вправо, пока не займет положение 
. При многократном повторении процесса будут заполняться позиции 
, 
и т. д. Действие выполняется до тех пор, пока вся последовательность не будет окончательно отсортирована. Очевидно, что часть массива, где элементы заняли свои окончательные позиции, могут не рассматриваться на следующих итерациях.
Пример сортировки пузырьковым методом массива 
( 
) приведен на рисунке 5.3. Здесь первая итерация рассмотрена подробно, с указанием всех перемещений, которые происходят на каждом шаге итерации. Для остальных итераций приведен лишь конечный результат.
| Итерация i | Результат сортировки | |||||||
| 1 | 40 40 40 40 40 40 40 40 | 61 61 8 8 8 8 8 8 | 8 8 61 38 38 38 38 38 | 38 38 38 61 61 61 61 61 | 112 112 112 112 112 10 10 10 | 10 10 10 10 10 112 3 3 | 3 3 3 3 3 3 112 83 | 83
83
83
83
83
83
83
|
| 2 | 8 | 38 | 40 | 10 | 3 | 61 | 
|
|
| 3 | 8 | 38 | 10 | 3 | 40 | 
|
|
|
| 4 | 8 | 10 | 3 | 38 | 
|
|
|
|
| 5 | 8 | 3 | 10 | 
|
|
|
|
|
| 6 | 3 | 8 | 
|
|
|
|
|
|
| Итог: | 3 | 8 | 10 | 38 | 40 | 61 | 83 | 112 |
|
|
|
Рис. 3.3. Пример сортировки пузырьковым методом
___ – текущие проверяемые элементы;
– операция взаимного обмена элементов;
– элемент, занявший окончательную позицию в отсортированной последовательности
На 6-й итерации не произошло ни одного обмена, следовательно, массив был полностью отсортирован.
Сортировка получила свое название, по подобию с процессом всплытия пузырька воздуха в воде. Если последовательность расположить не горизонтально, а вертикально, на каждой итерации максимальный элемент неотсортированной последовательности (самый «большой пузырек») будет «всплывает» наверх, занимая свою конечную позицию.
Достоинством пузырьковой сортировки является простота ее программной реализации. Однако вопрос о том, какой метод сортировки реализуется проще – метод вставок, метод прямого выбора или пузырьковый – не имеет однозначного ответа. В общем случае быстродействие пузырькового метода не превосходит другие рассмотренные.
Метод пузырьковой сортировки хорошо работает на практически отсортированных массивах за счет снижения числа перестановок. Метод позволяет легко определить момент полной упорядоченности массива проверкой отсутствия перестановок на итерации и исключить последние «пустые» итерации сортировки.
|
|
|
Шейкерная сортировка (сортировка перемешиванием)
Шейкерная сортировка реализует на каждой итерации пузырьковую сортировку, меняя каждый раз при этом направление просмотра.
Пример шейкерной сортировки массива ( ) приведен на рисунке 5.4. Подробно шаги первой итерации рассмотрены на рисунке 5.3.
| Итерация i | Результат сортировки | |||||||
| 1 | 40 | 61 | 8 | 38 | 112 | 10 | 3 | 83 |
| 2 | 40 | 8 | 38 | 61 | 10 | 3 | 83 |
|
| 3 | 
| 40 | 8 | 38 | 61 | 10 | 83 |
|
| 4 |
| 8 | 38 | 40 | 10 | 61 |
|
|
| 5 |
| 
| 10 | 38 | 40 | 61 |
|
|
| Итог: | 3 | 8 | 10 | 38 | 40 | 61 | 83 | 112 |
Рис. 5.4. Пример сортировки шейкерным методом
– перемещение элемента;
– элемент, занявший окончательную позицию в отсортированной последовательности
Применение шейкерного метода позволило выполнить сортировку за 5 итераций: на итерации 5 не произошло ни одного обмена и сортировка была прекращена.
|
|
|
Быстрая сортировка
Быстрая сортировка (quicksort, qsort) является одним из самых эффективных универсальных алгоритмов упорядочивания элементов массива, что объясняет его высокую популярность. В среднем алгоритм имеет 
обменов при упорядочивании массива из n элементов. Алгоритм реализует сортировку «на месте», то есть не требует выделения дополнительной памяти для хранения вспомогательных массивов.
В алгоритме реализуется принцип «разделяй и властвуй». Он является усовершенствованным вариантом алгоритмов прямого обмена. Основное отличие алгоритма быстрой сортировки заключается в том, что на каждой итерации выполняется попытка перестановки наиболее удаленных друг от друга элементов, которые при этом разделяются на два подмассива.
Алгоритм состоит из следующих основных шагов:
1. Выбор опорного элемента. Опорным может быть выбран любой элемент массива. От выбора опорного элемента зависит эффективность алгоритма. При этом не существует универсального способа выбора опорного элемента. На практике в качестве опорного выбирают средний, случайный элемент или медиану первого, среднего и последнего элементов (ее вычисление трудоемко и оправдано лишь для больших массивов).
|
|
|
2. Последовательное сравнение элементов с опорным и пересортировка элементов на две группы: большие опорного элемента и меньшие опорного элемента. В результате пересортировки элементы будут располагаться таким образом, что элементы, меньшие опорного, будут находиться слева от него, а большие – справа. При этом сам опорный элемент занимает свою окончательную позицию в отсортированном массиве и не меняет своего положения на последующих итерациях.
3. Рекурсивное выполнение шагов 1 и 2 для каждого из полученных подмассивов. Рекурсия не применяется к пустому массиву или массиву, состоящему только из одного элемента.
Ключевым этапом быстрой сортировки является разбиение массива на две группы. Наиболее эффективным вариантом реализации данного действия считается так называемое разбиение Хоара. В алгоритме разбиения используются два индекса – один устанавливается в начало массива, второй – в конец. На каждой итерации они приближаются друг к другу, при этом осуществляется поиск элемента, который больше опорного и расположен слева от него и того, который меньше опорного и расположен справа от него. При нахождении пары таких элементов они меняются местами. Поиск таких пар элементов и обмен продолжается до тех пор пока индексы не пересекутся.
Пример быстрой сортировки массива ( ) приведен на рисунке 5.5. В качестве опорного выбираются центральные элементы массивов.
| Итерация i | Результат сортировки | |||||||||||||
| 1 Начальная позиция маркеров | 40
| 61
| 8
|
| 112 | 10 | 3
| 83 | ||||||
| Найдена пара для обмена | 40 | 61
| 8
|
| 112
| 10
| 3 | 83
| ||||||
| Найдена пара для обмена | 3 | 61
| 8
|
| 112
| 10
| 40 | 83
| ||||||
| Индексы пересеклись | 3 | 10 | 8
|
| 112
| 61 | 40 | 83
| ||||||
| 2 | 3 |
| 8
|
| 112
|
| 40 | 83
| ||||||
| 3 |
| 8
|
| 40
|
| 112 | 83
| |||||||
| 3 | 8
|
|
|
|
|
| 83
| |||||||
|
| 8
|
|
|
|
| 83 |
| |||||||
|
| 8
|
|
|
|
| 
|
| |||||||
|
|
|
|
|
| |||||||||
| Итог сортировки | 3 | 8 | 10 | 38 | 40 | 61 | 83 | 112 | ||||||
Рис. 5.5. Пример быстрой сортировки
– указатели на текущие позиции левого и правого маркеров ;
– опорный элемент;
– элемент, занявший окончательную позицию в отсортированной последовательности
Сортировка выбором
Это семейство методов сортировки основано реализует идею многократного выбора и замены элементов между собой. Методы требуют наличия всех исходных элементов до начала сортировки.
Дата добавления: 2020-01-07; просмотров: 483; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!