Сортировка обменом паскаль — Мир ПК

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

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

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

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

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

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

Procedure Obmen(Var a : Array1); Var i,j,f,g:integer; Begin for i:=n downto 2 do for j:=1 to i-1 do if a[j]>a[j+1] then begin f:=a[j]; a[j]:=a[j+1]; a[j+1]:=f; end; End;

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

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

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

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

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

Procedure QuickSort (Left, Right : integer; Massiv : Array1); Var i, j, x, y : integer; Begin i := Left; j := Right; x := Massiv[(Left+Right) div 2];<> repeat while Massiv[i] x do Dec(j); if i j; if Left

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

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

• 
• 
• 
• 
• 

Категории:

Свежие
комментарии:

Полина:
Мы такие задачи решаем в 6 классе. Как раз вчера по инф..

Олег:
Спасибо, все очень подробно написано..

Калужский Александр:
Можете мне заказать.

Сортировка пузырьком (Pascal)

Сегодня мы разберем сортировку методом «пузырька». Данный алгоритм часто проходится в школах и университетах, поэтому будем использовать язык Pascal. И, так, что такое сортировка? Сортировка — это упорядочение элементов от меньшего к большему (сортировка по возрастанию) или от большего элемента к меньшему (сортировка по убыванию). Сортируют обычно массивы.

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

Плюсы:

• Простота реализации алгоритма
• Красивое название

Минусы:

• Один из самых медленных методов сортировки (Время выполнения квадратично зависит от длины массива n 2 )
• Почти не применяется в реальной жизни (используется в основном в учебных целях)

Пусть есть у нас некий массив: 3 1 4 2

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

Вернемся к нашему массиву : 3 1 4 2
Берем первый элемент «3» сравниваем со следующим «1». Т.к. «3» > «1», то меняем местами:
1 3 4 2
Теперь сравниваем «3» и «4», тройка не больше четвёрки, значит ничего не делаем. Далее, сравниваем «4» и «2». Четыре больше, чем два — значит меняем местами: 1 3 2 4 . Цикл закончился. Значит самый большой элемент уже должен стоять на своём месте!! Видим, что у нас так и произошло. Где бы «4» (наш самый большой элемент) не находился — он всё равно, после прохождения циклом всего массива, будет последним. Аналогия — как пузырёк воздуха всплывает в воде — так и наш элемент, всплывает в массиве. Поэтому и алгоритм, называется «Пузырьковая сортировка». Чтобы расположить следующий элемент, необходимо, начать цикл сначала, но последний элемент можно уже не рассматривать, потому что он стоит на своём месте.

Сравниваем «1» и «3» — ничего не меняем.
Сравниваем «3» и «2» — Три больше двух, значит меняем местами. Получается : 1 2 3 4 . Второй цикл закончили. Мы сделали уже два цикла — значит, с уверенностью можно сказать, что у нас, два последних элемента уже отсортированы. Осталось нам отсортировать третий элемент, а четвёртый, встанет в нужное место, автоматически. Ещё раз, сравниваем первый элемент и второй — видим, что у нас уже всё на своих местах, значит, массив, можно считать, отсортированный по возрастанию элементов.

Теперь осталось запрограммировать данный алгоритм на языке Pascal.
Вот результат:

А вот видеоурок

Урок 28. Сортировка массива

Урок из серии: «Программирование на языке Паскаль»

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

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

Сортировка массива методом простого выбора

При сортировке массива методом выбора применяется базовый алгоритм поиска максимального (минимального) элемента и его номера.

Алгоритм сортировки массива методом выбора:

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

Для упорядочения массива потребуется (n-1) просмотров массива. В процессе сортировки будет увеличиваться отсортированная часть массива, а неотсортированная, соответственно, уменьшаться.

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

Задача 1. Массив из 10 элементов отсортировать по возрастанию методом простого перебора.

Напишем процедуру. Входным параметром для неё будет массив. Он же будет и выходным параметром. Поэтому описываем его как параметр-переменная (с ключевым словом var).

В процедуре внешний цикл по i — определяет длину рассматриваемой части массива. Она будет изменяться от n до 2.

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

Программный код процедуры:

Программный код основной программы:

Процесс упорядочения элементов в массиве по возрастанию методом отбора:

Номер элемента	1	2	3	4	5
Исходный массив	8	7	5	4	2
Первый просмотр	2	7	5	4	8
Второй просмотр	2	4	5	7	8
Третий просмотр	2	4	5	7	8
Четвертый просмотр	2	4	5	7	8

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

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

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

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, с помощью которого можно в пошаговом режиме просмотреть визуализацию этих (и не только этих) сортировок.