Сортировка массива способом обмена

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

Реализация сортировки методом «пузырька» на Си

Анализ алгоритма

Число сравнений в алгоритме прямого обмена

С = (n 2 — n)/2,

а минимальное, среднее и максимальное число перемещений элементов равно соответственно

Mmin = 0,

Mср = 3(n2 — n)/2,

Mmax = 3(n2 — n)/4.

Резюме : «обменная сортировка» представляет собой нечто среднее между сортировками с помощью включений и с помощью выбора; фактически в пузырьковой сортировке нет ничего ценного, кроме привлекательного названия.

Источник

Методы сортировки массива

Тема: Сортировка методом простого обмена. Рекурсивная сортировка.

Слева направо поочередно сравниваются два соседних элемента, и если их взаимное расположение не соответствует заданному условию упорядоченности, то они меняются местами. Далее берутся два следующих соседних элемента и так далее до конца массива.

После одного такого прохода на последней n-ой позиции массива будет стоять максимальный (или минимальный) элемент («всплыл» первый «пузырек»). Поскольку максимальный (или минимальный) элемент уже стоит на своей последней позиции, то второй проход обменов выполняется до (n-1)-го элемента. И так далее. Всего требуется (n-1) проход.

Задание. В тетради начертите схему работы рассмотренного алгоритма произвольно выбранного массива.

Рассмотрите процедуру, реализующую выше рассмотренный алгоритм:

Задание. Составьте программу сортировки одномерного массива рассмотренным методом.

Сортировка массива с помощью рекурсии

Рассмотрим использование рекурсии для построения алгоритма сортировки значений массива.

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

Рассмотрите процедуру, упорядочивающую по возрастанию значения из массива Massiv в диапазоне индексов Left..Right.

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

Источник

Сортировка методом обмена

Delphi site: daily Delphi-news, documentation, articles, review, interview, computer humor.

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

На рис. 5.16 цифрой 1 обозначено исходное состояние массива и перестановки на первом проходе, цифрой 2 — состояние после перестановок на первом проходе и перестановки на втором проходе и т. д.

Рис. 5.16. Процесс сортировки массива

Рис. 5.17. Диалоговое окно программы Сортировка методом обмена

На рис. 5.17 приведено диалоговое окно программы сортировки массива методом обмена.

Процедура сортировки, текст которой приведен в листинге 5.10, запускается нажатием кнопки Сортировка (ви1:1:оп1). Значения элементов массива вводятся из ячеек компонента 31;г:тдСг1а1. Во время сортировки, после выполнения очередного цикла обменов элементов массива, программа выводит массив в поле метки ьаЬе12.

I Листинг 5.10. Сортировка массива методом обмена

к:integer; // текущий элемент массива

i:integer; // индес для ввода и вывода массива

changed:boolean; // TRUE, если в текущем цикле были обмены

buf:integer; // буфер для обмена элемнтами массива

// сортирвка массива repeat

changed:=FALSE; // пусть в текущем цикле нет обменов

until not changed; // если не было обменов, значит // массив отсортирован

Следует отметить, что максимальное необходимое количество циклов проверки соседних элементов массива равно количеству элементов массива минус один. Вместе с тем возможно, что массив реально будет упорядочен за меньшее число циклов. Например, последовательность чисел 5 1 2 3 4, если ее рассматривать как представление массива, будет упорядочена за один цикл, и выполнение оставшихся трех циклов не будет иметь смысла.

Поэтому в программу введена логическая переменная changed, которой перед выполнением очередного цикла присваивается значение false. Процесс сортировки (цикл repeat) завершается, если после выполнения очередного цикла проверки соседних элементов массива (цикл for) ни один элемент массива не был обменен с соседним, и, следовательно, массив уже упорядочен.

Рис. 5.18. Пример работы программы сортировки массива методом обмена

На рис. 5.18 приведено диалоговое окно программы сортировки массива методом обмена после завершения процесса сортировки.

Источник

Сортировки обменами

Если описать в паре предложений по какому принципу работают сортировки обменами, то:

1. Попарно сравниваются элементы массива
2. Если элемент слева * больше элемента справа, то элементы меняются местами
3. Повторяем пункты 1-2 до тех пор, пока массив не отсортируется

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

Сразу прошу прощения за повторение общеизвестного материала, вряд ли хоть один из алгоритмов в статье станет для Вас откровением. Про эти сортировки на Хабре писалось уже неоднократно (в том числе и мной — 1, 2, 3) и спрашивается, зачем опять возвращаться к этой теме? Но раз уж я решил написать связную серию статей про все сортировки на свете, мне приходится хотя бы в экспресс-варианте пройтись и по обменным способам. При рассмотрении следующих классов уже будет много новых (и мало кому известных) алгоритмов, заслуживающих отдельных интересных статей.

Традиционно к «обменникам» относят сортировки, в которых элементы меняются (псевдо)случайным образом (bogosort, bozosort, permsort и т.п.). Однако я не стал их включать в этот класс, так как в них отсутствуют сравнения. Про эти сортировки будет отдельная статья, где мы вдоволь пофилософствуем о теории вероятности, комбинаторике и тепловой смерти Вселенной.

Придурковатая сортировка :: Stooge sort

1. Сравниваем (и при необходимости меняем) элементы на концах подмассива.
2. Берём две трети подмассива от его начала и к этим 2/3 рекурсивно применяем общий алгоритм.
3. Берём две трети подмассива от его конца и к этим 2/3 рекурсивно применяем общий алгоритм.
4. И опять берём две трети подмассива от его начала и к этим 2/3 рекурсивно применяем общий алгоритм.

Изначально подмассив — весь массив. А дальше рекурсия дробит родительский подмассив на 2/3, производит сравнения/обмены на концах раздробленных отрезков и в итоге всё упорядочивает.

Выглядит шизофренично, но тем не менее это на 100% корректно.

Вялая сортировка :: Slow sort

И здесь мы наблюдаем рекурсивную мистику:

1. Если подмассив состоит из одного элемента, то завершаем рекурсию.
2. Если подмассив состоит из двух и более элементов, то делим его пополам.
3. Применяем рекурсивно алгоритм к левой половинке.
4. Применяем рекурсивно алгоритм к правой половинке.
5. Сравниваются элементы на концах подмассива (и меняются при необходимости).
6. Рекурсивно применяем алгоритм к подмассиву без последнего элемента.

Изначально подмассив — это весь массив. А рекурсия будет дальше половинить, сравнивать и менять пока всё не отсортирует.

Похоже на бред, однако массив упорядочивается.

Почему корректно работают StoogeSort и SlowSort?

Пытливый читатель задаст резонный вопрос: а почему эти два алгоритма вообще срабатывают? Они вроде простые, а не особо-то очевидно, что так можно что-то отсортировать.

Давайте сначала разберём Slow sort. Последний пункт этого алгоритма намекает, что рекурсивные усилия вялой сортировки направлены только на то, чтобы в правую крайнюю позицию поставить наибольший элемент в подмассиве. Это особенно заметно, если применить алгоритм к обратно упорядоченному массиву:

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

В Stooge sort происходит похожая магия:

На самом деле тут тоже делается упор на максимальных элементах. Только Slow sort их в конец перемещают по одному, а Stooge sort треть элементов подмассива (самые крупные из них) задвигает в крайнюю справа треть ячеечного пространства.

Переходим к алгоритмам, где уже всё достаточно очевидно.

Туповатая сортировка :: Stupid sort

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

Гномья сортировка :: Gnome sort

Почти то-же самое, но тут сортировка при обмене не возвращается в самое начало массива, а делает всего один шаг назад. Этого, оказывается, вполне достаточно чтобы всё отсортировать.

Оптимизированная гномья сортировка

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

Пузырьковая сортировка :: Bubble sort

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

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

Оптимизированная пузырьковая сортировка

Можно немного выгадать на проходах по началу массива. В процессе первые элементы оказывается временно упорядоченными друг относительно друга (эта отсортированная часть постоянно меняется в размерах — то уменьшается, то увеличивается). Это легко фиксируется и при новой итерации можно просто перепрыгнуть через группу таких элементов.
_{(Проверенную реализацию на Питоне добавлю сюда чуть позже. Не успел подготовить.)}

Шейкерная сортировка :: Shaker sort
(Коктейльная сортировка :: Cocktail sort)

Разновидность пузырька. На первом проходе как обычно — задвигаем максимум в конец. Потом резко разворачиваемся и толкаем минимум в начало. Отсортированные крайние области массива увеличиваются в размерах после каждой итерации.

Чётно-нечётная сортировка :: Odd-even sort

Снова итерации по попарному сравнению соседних элементов при движении слева-направо. Только сначала сравниваем пары у которых первый элемент — нечётный по счёту, а второй — чётный (т.е. первый и второй, третий и четвёртый, пятый и шестой и т.д.). А потом наоборот — чётный + нечётный (второй и третий, четвёртый и пятый, шестой и седьмой и т.д.). В этом случае многие крупные элементы массива на одной итерации одновременно делают один шаг вперёд (в пузырьке самый крупный за итерацию доходит до конца, но остальные немаленькие практически все остаются на месте).

Кстати, это изначально была параллельная сортировка со сложностью O(n). Надо будет в AlgoLab реализовать в разделе «Параллельные сортировки».

Сортировка расчёской :: Comb sort

Самая удачная модификация пузырька. Алгоритм по скорости соперничает с быстрой сортировкой.

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

Быстрая сортировка :: Quick sort

Ну и самый продвинутый обменный алгоритм.

1. Делим массив пополам. Средний элемент — опорный.
2. Движемся от левого края массива вправо, до тех пор пока не обнаружим элемент, который больше опорного.
3. Движемся от правого края массива влево, до тех пор пока не обнаружим элемент, который меньше опорного.
4. Меняем местами два элемента, найденные в пунктах 2 и 3 .
5. Продолжаем выполнять пункты 2-3-4 пока в результате обоюдного движения не произойдёт встреча.
6. В точке встречи массив делится на две части. К каждой части рекурсивно применяем алгоритм быстрой сортировки.

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

K-сортировка :: K-sort

На Хабре опубликован перевод одной из статей, где сообщается о модификации QuickSort, которая на 7 миллионах элементов обгоняет пирамидальную сортировку. Кстати, само по себе это сомнительное достижение, ибо классическая пирамидальная сортировка не бьёт рекордов быстродействия. В частности, её асимптотическая сложность ни при каких условиях не достигает O(n) (особенность данного алгоритма).

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

1. Заявляем о изобретении супер-алгоритма сортировки.
2. Подкрепляем заявление неработающим и непонятным псевдокодом (типа, умным и так ясно, а дуракам понять всё равно не дано).
3. Приводим графики и табицы, якобы демонстрирующие практическую скорость алгоритма на больших данных. Ввиду отсутствия реально работающего кода всё равно никто не сможет ни проверить ни опровергнуть эти статистические выкладки.
4. Публикуем ахинею на Arxiv.org под видом научной статьи.
5. PROFIT.

Может, я зря наговариваю на людей и на самом деле алгоритм рабочий? Кто-нибудь может пояснить как работает k-sort?

UPD. Мои огульные обвинения авторов сортировки в мошенничестве оказались несостоятельными 🙂 Пользователь jetsys разобрался в псевдокоде алгоритма, написал работающую версию на PHP и прислал мне её в личных сообщениях:

Анонс

Это всё была теория, пора переходить к практике. Следующая статья — тестирование сортировок обменами на разных наборах данных. Мы узнаем:

• Какая сортировка наихудшая — придурковатая, вялая или туповатая?
• Сильно ли помогают оптимизации и модификации пузырьковой сортировке?
• При каких условиях медленные алгоритмы легко уделают по скорости QuickSort?

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

Ссылки

Excel-приложение AlgoLab, с помощью которого можно в пошаговом режиме просмотреть визуализацию этих (и не только этих) сортировок.

Источник