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

Презентация на тему “Сортировка обменом(Сортировка пузырьком)”

Скачать презентацию (0.21 Мб)
3 загрузки
0.0 оценка

ВКонтакте

Одноклассники

Facebook

Твиттер

Телеграм

Ваша оценка презентации

Оцените презентацию по шкале от 1 до 5 баллов

Посмотреть и скачать бесплатно презентацию по теме “Сортировка обменом(Сортировка пузырьком)”. pptCloud.ru — каталог презентаций для детей, школьников (уроков) и студентов.

Форматpptx (powerpoint)
Количество слайдов6
Слова
КонспектОтсутствует

Слайд 1МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Вятский государственный университет» (ФГБОУ ВПО «ВятГУ») Работу выполнили студенты группы ИВТ-11: Веселов РоманЖуков ДмитрийКараваев АртемМакаров АлексейПентин МаксимСеливанов ЯковШеромов Дмитрий
Слайд 2Сортировка пузырьком — простейший для понимания и реализации алгоритм сортировки. Эффективен он лишь для небольших массивов. Недостатком является высокая сложность алгоритма: O(n²). Алгоритм считается учебным и практически не применяется вне учебной литературы, вместо него на практике применяются более эффективные алгоритмы сортировки. В то же время метод сортировки обменами лежит в основе некоторых более совершенных алгоритмов, таких как шейкерная сортировка, пирамидальная сортировка и быстрая сортировка. Алгоритм является устойчивым (не меняет взаимного расположения равных элементов). Алгоритм не использует дополнительной памяти, т.е. все действия осуществляются на одном и том же массиве.
Слайд 3Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются N-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим наибольшим элементом, а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма).
Слайд 4Возьмём массив с числами «5 1 4 2 8» и отсортируем значения по возрастанию, используя сортировку пузырьком. Выделены те элементы, которые сравниваются на данном этапе. Первый проход: (5 14 2 8) (1 54 2 8) (1 5 42 8) (1 4 5 2 8) (1 4 5 2 8) (1 4 2 5 8) (1 4 2 5 8) (1 4 2 5 8) Второй проход: (1 42 5 8) (1 42 5 8) (1 4 25 8) (1 2 45 8) (1 2 4 5 8) (1 2 4 5 8) (1 2 4 5 8) (1 2 4 5 8) Здесь алгоритм сравнивает два первых элемента и меняет их местами. Меняются местами 5 и 4, т. к. 5>4. Меняются местами 5 и 4, т. к. 5>2. Алгоритм не меняет местами элементы, т. к. 5
Слайд 5program sort_obmen; uses crt; vara: array [1..100] of byte; n,x,i,j:integer; begin clrscr; writeln('Введите размер массива'); readln(n); for i:= 1 to n do begin write('Введите ',i,'-й элемент массива '); read(a[i]); end; writeln('Введенный массив:'); for i:= 1 to n do write(a[i],' '); writeln; for j:=1 to n-1 do begin for i:=1 to n-1 do if a[i]>a[i+1] then begin x:=a[i]; a[i]:=a[i+1]; a[i+1]:=x; end; end; writeln('Отсортированный массив:'); for i:=1 to n do write(a[i],' '); readln; end.

Посмотреть все слайды

Источник: https://pptcloud.ru/raznoe/sortirovka-obmenom-sortirovka-puzyrkom

Моу сош с. Камышки творческая работа

Сохрани ссылку в одной из сетей:

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

Рассмотрим сортировку обменом (метод “Пузырька”).

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

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

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

2 в приложении 6), то можно увидеть, что большие элементы, подобно пузырькам воздуха в воде, “всплывают” на соответствующую позицию. Поэтому “сортировку”, таким образом, называют еще сортировкой методом “пузырька”, или “пузырьковой” сортировкой.Сортировка методом простого обмена может быть применена для любого массива.

Итак, в сортировке “обменом” все соседние элементы попарно сравниваются друг с другом и меняются местами, если предшествующий элемент больше последующего. То есть мы опять основываемся на уже отработанных алгоритмах перестановки элементов.

Описание этого метода подробнее в приложении 6.

“Шейкер” – сортировка.

Несмотря на все сделанные выше усовершенствования, “пузырьковая” сортировка следующего ( почти упорядоченного! ) массива 5, 7, 12, 28, 36, 85, 2 будет проведена за семь проходов. Это связано с тем, что при сортировке, рассматриваемым методом, за один проход элемент не может переместиться влево больше чем на одну позицию.

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

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

Такой метод сортировки называется “шейкер”-сортировкой ( от английского слова shake – трясти, встряхивать ). Его работа показана на примере сортировки массива из 8 элементов (на рис. 3 в приложении 7). Алгоритмы этого метода подробно изложены в приложении 7.

Сортировка подсчетом

Этот простой и легкий для понимания метод заключается в том, что каждый элемент массива сравнивается со всеми остальными. Место каждого элемента в отсортированном массиве зависит от числа элементов, меньших его. Иными словами, если некоторый элемент превышает 13 других, то его место в упорядоченной последовательности – 14.

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

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

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

На k-м шаге считается, что часть массива, содержащая первые k-1 элементов, уже упорядочена, то есть a[1] < a[2]< . . . < a[k-l].

Далее необходимо взять k-й элемент и подобрать для него такое место в отсортированной части массива, чтобы после его вставки упорядоченность не нарушилась, то есть надо найти такое j (1

Источник: https://refdb.ru/look/2968346-p2.html

3678 ТЕХНОЛОГИЯ ПРОГРАММИРОВАНИЯ – Страница 4

Страница 4 из 6

В настоящее время известно несколько десятков различных методов сортировки. Они различаются сложностью, быстро- действием и объемом занимаемой памяти.

Процесс сортировки записей состоит из просмотров и сравнений ключей, а также из расположения элементов в соответствии с результатом сравнения.

1.2. Алгоритмы сортировки

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

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

При сортировке методом обмена два определенным образом выбранных элемента, расположение которых не соответствует порядку, меняют местами. Этот процесс повторяется до тех пор, пока остаются такие пары.

К обменным относятся следующие сортировки: парный обмен, стандартный обмен (метод “пузырька”), шейкер-сортировка, метод Бэтчера, “быстрая сортировка”, просеивание (“челночная” сортировка) и др.

Все эти методы различаются между собой способами просмотра и выбора в сортируемой последовательности элементов для сравнения.

1.2.1.1. Метод стандартного обмена

Этот метод основан на попарном сравнении ключей соседних записей. Если порядок следования записей в очередной паре неправилен, то эти элементы обмениваются местами. При первом просмотре ключ 1-й записи сравнивается с ключом 2-й записи и, если 2-й меньше, то они меняются местами. Затем ключ, расположенный во 2-й позиции, сравнивается с ключом из 3-й позиции.

Обмен происходит, если меньший из них находится в 3-й позиции. После этого позиция 3 сравнивается с позицией 4, позиция 4 – с позицией 5 и т.д. Когда позиция N-1 сравнивается с позицией N, просмотр заканчивается. После первого просмотра запись с наибольшим ключом займет N-ю позицию, а минимальный элемент переместится на одну позицию к началу последовательности.

Второй просмотр идентичен первому лишь с той разницей, что он заканчивается после сравнения ключей N-2-й и N-1-й записей.

Так как на каждом из проходов очередные наибольшие элементы занимают соответственно позиции N, N-1, N-2 и т.д., то не более как за N-1 проход исходная последовательность будет упорядочена.

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

Структурограмма алгоритма сортировки методом стандартного обмена приведена на рис. 1.

Пример. Пусть требуется упорядочить в порядке возрастания значений следующий массив чисел из 8 элементов:

К(1) К(2) К(3) К(4) К(5) К(6) К(7) К(8)

25 57 48 37 12 92 86 33.

На первом просмотре производятся следующие сравнения и обмены (в начале просмотра признаку обмена FLAG присваивается значение, равное 0): К(1) с К(2) (25 с 57) нет обмена

К(2) с К(3) (57 с 48) обмен (FLAG=1)

К(3) с К(4) (57 с 37) обмен

К(4) с К(5) (57 с 12) обмен

К(5) с К(6) (57 с 92) нет обмена

К(6) с К(7) (92 с 86) обмен

К(7) с К(8) (92 с 33) обмен.

Таким образом, после 1-го просмотра элементы массива будут

располагаться в следующем порядке:

К(1) К(2) К(3) К(4) К(5) К(6) К(7) К(8)

25 48 37 12 57 86 33 92,

а признак обмена FLAG=1.

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

На втором просмотре производятся следующие сравнения и обмены (первоначально FLAG=0):

К(1) с К(2) (25 с 48) нет обмена

К(2) с К(3) (48 с 37) обмен (FLAG=1)

К(3) с К(4) (48 с 12) обмен

К(4) с К(5) (48 с 57) нет обмена

К(5) с К(6) (57 с 86) нет обмена

К(6) с К(7) (86 с 33) обмен.

После второго просмотра элементы массива будут располагаться в следующей последовательности:

К(1) К(2) К(3) К(4) К(5) К(6) К(7) К(8)

25 37 12 48 57 33 86 92.

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

просмотр 3 (FLAG=0) 25 12 37 48 33 57 86 92 (FLAG=1)

просмотр 4 (FLAG=0) 12 25 37 33 48 57 86 92 (FLAG=1)

просмотр 5 (FLAG=0) 12 25 33 37 48 57 86 92 (FLAG=1)

просмотр 6 (FLAG=0) 12 25 33 37 48 57 86 92 (FLAG=0).

Так как после 6-го просмотра признак обмена имеет значение 0, сортировка окончена.

1.2.1.2. Просеивание (“челночная” сортировка)

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

Пример. Исходная последовательность

К(1) К(2) К(3) К(4) К(5) К(6) К(7) К(8)

25 57 48 37 12 92 86 33.

Первоначально, как и в методе “пузырька”, сравниваются 1-й и 2-й элементы. Так как их порядок правильный, то они местами не меняются. Затем сравниваются 2-й и

3-й элементы. Так как 57 больше 48, то они меняются местами. При J=2 и I=2 последовательность будет иметь вид

К(1) К(2) К(3) К(4) К(5) К(6) К(7) К(8)

25 48 57 37 12 92 86 33.

Далее согласно алгоритму 2-й элемент сравнивается с 1-м. Порядок их правильный, и ничего не происходит.

Затем снова, как в методе “пузырька”, сравниваются 3-й и 4-й

элементы. Они меняются местами. 3-й

элемент сравнивается со 2-м, и они также меняются. 2-й элемент сравнивается с 1-м, и так как порядок их правильный, они остаются на своих местах. После завершения этапа при J=3 последовательность будет иметь следующий вид:

К(1) К(2) К(3) К(4) К(5) К(6) К(7) К(8)

25 37 48 57 12 92 86 33.

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

К(1) К(2) К(3) К(4) К(5) К(6) К(7) К(8)

J=4 12 25 37 48 57 92 86 33

J=5 12 25 37 48 57 92 86 33

J=6 12 25 37 48 57 86 92 33

J=7 12 25 33 37 48 57 86 92.

Для ускорения работы алгоритма при каждом возврате регистрируется факт наличия или отсутствия обмена. Возврат, в результате которого не было произведено ни одного обмена, заканчивает просмотр. Структурограмма алгоритма сортировки методом просеивания представлена на рис. 2.

1.2.1.3. Шейкер-сортировка

Особенность шейкер-сортировки заключается в том, что в отличие от метода “пузырька” запоминается не только факт обмена, но и текущая позиция обмена, а просмотры чередуются попеременно в противоположных направлениях в некотором интервале.

На 1-м просмотре производится сравнение ключей соседних записей, например, слева направо, начиная с первой позиции, и фиксируется позиция L последнего обмена. На 2-м просмотре сравниваются ключи записей справа налево, начиная с L-го элемента, и фиксируется позиция R последнего обмена. В результате 2-х просмотров запись с наибольшим ключом займет

N-ю позицию, а запись с наименьшим ключом – 1-ю.

Затем снова слева направо сравниваются ключи записей, начиная с R-й позиции и кончая L-й и т.д. Сортировка заканчивается, если в результате очередного просмотра не производится обмен. Структурограмма алгоритма шейкер-сортировки приведена на рис. 3.

Пример. Исходная последовательность

К(1) К(2) К(3) К(4) К(5) К(6) К(7) К(8)

25 57 48 37 12 92 86 33.

На первом просмотре производятся сравнения и обмены так же, как в методе “пузырька”( см. п. 1.2.1.1 ). Последний обмен производится в позиции L=7, а последовательность после 1-го просмотра имеет вид

К(1) К(2) К(3) К(4) К(5) К(6) К(7) К(8)

25 48 37 12 57 86 33 92.

Второй просмотр производится справа налево, начиная с 7-й позиции (FLAG=0):

К(7) c К(6) (33 с 86) обмен (FLAG=1)

К(6) с К(5) (33 с 57) обмен

К(5) с К(4) (33 с 12) нет обмена

К(4) с К(3) (12 с 37) обмен

К(3) с К(2) (12 с 48) обмен

К(2) с К(1) (12 с 25) обмен.

Последний обмен производится во 2-й позиции R=2, а последовательность после 2-го просмотра имеет следующий вид:

К(1) К(2) К(3) К(4) К(5) К(6) К(7) К(8)

12 25 48 37 33 57 86 92.

Последующие просмотры выглядят следующим образом:

3: (R=2, L=7, FLAG=0) 12 25 37 33 48 57 86 92 (L=4, FLAG=1);

4: (R=2, L=4, FLAG=0) 12 25 33 37 48 57 86 92 (R=4, FLAG=1);

5: (R=4, L=4, FLAG=0) 12 25 33 37 48 57 86 92 (FLAG=0).

После 5-го просмотра сортировка заканчивается.

1.2.2. Сортировка выбором

Основная идея метода сортировки выбором состоит в том, чтобы идти по шагам i=1,2,…,N-1, находя на i-м шаге среди неотсортированных записей запись с наименьшим ключом и каким-либо образом помещая ее на соответствующее место.

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

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

Просмотр последовательности записей, длина которой уменьшается на единицу при каждом просмотре, заканчивается, когда в ней остается только одна запись, занимающая последнюю позицию. В течении 1-го просмотра ищется запись с наименьшим ключом, которая меняется местами с первой записью.

Второй просмотр идентичен 1-му с той лишь разницей, что первая позиция исключается из рассмотрения. Третий просмотр начинается сравнением ключа из 3-й позиции и т.д. Эта процедура заканчивается, когда свое место занимает (N-1)-я запись.

Структурограмма алгоритма сортировки методом выбора с обменом приведена на рис. 4.

Пример. Исходная последовательность

К(1) К(2) К(3) К(4) К(5) К(6) К(7) К(8)

25 57 48 37 12 92 86 33.

В результате 1-го просмотра находится наименьший элемент 12,занимающий 5-ю позицию. Он меняется местами с элементом 25 на 1-й позиции.

К(1) К(2) К(3) К(4) К(5) К(6) К(7) К(8)

12 57 48 37 25 92 86 33.

Остальные просмотры выглядят следующим образом:

К(1) К(2) К(3) К(4) К(5) К(6) К(7) К(8)

Просмотр 2: 12 25 48 37 57 92 86 33

Просмотр 3: 12 25 33 37 57 92 86 48

Просмотр 4: 12 25 33 37 57 92 86 48

Просмотр 5: 12 25 33 37 48 92 86 57

Просмотр 6: 12 25 33 37 48 57 86 92

Просмотр 7: 12 25 33 37 48 57 86 92.

1.2.3. Сортировка вставками

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

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

Алгоритм сортировки простыми вставками проходит через этапы j=2,3,…,N. На j-м этапе запись Х(J) вставляется на свое правильное место среди Х(1), Х(2),…, Х(j-1).

При вставке запись Х(j) временно размещается в S и просматриваются записи Х(j-1), Х(j-2),…, Х(1); их ключи сравниваются с ключом T записи S и записи сдвигаются вправо, если обнаруживается, что их ключи больше ключа записи S.

Структурограмма алгоритма сортировки методом вставки представлена на рис. 5.

Пример. Исходная последовательность

К(1) К(2) К(3) К(4) К(5) К(6) К(7) К(8) K(9) K(10) K(11)

3 11 6 4 9 5 7 8 10 2 1.

При J=2 элемент K(2) сравнивается с К(1), и так как К(2)>К(1), то вставки нет. При J=3 элемент К(3) сравнивается с К(2) и К(1) и вставляется на место второго элемента К(2), а элемент К(2) предварительно сдвигается вправо на одну позицию. Сортируемая последовательность далее принимает вид

К(1) К(2) К(3) К(4) К(5) К(6) К(7) К(8) K(9) K(10) K(11)

J=4 : 3 4 6 11 9 5 7 8 10 2 1

J=5 : 3 4 6 9 11 5 7 8 10 2 1

J=6 : 3 4 5 6 9 11 7 8 10 2 1

J=7 : 3 4 5 6 7 9 11 8 10 2 1

J=8 : 3 4 5 6 7 8 9 11 10 2 1

J=9 : 3 4 5 6 7 8 9 10 11 2 1

J=10: 2 3 4 5 6 7 8 9 10 11 1

J=11: 1 2 3 4 5 6 7 8 9 10 11.

1.2.4. Метод Шелла (сортировка с убывающим шагом)

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

При этом число частей уменьшается, а их длина увеличивается. Сортировка заканчивается просмотром с Н=1. В методе Шелла первоначально Н устанавливается равным INT(N/2), а затем сокращается вдвое. Структурограмма метода Шелла с сортировкой вставкой отдельных частей приведена на рис.

Пример. Исходная последовательность

К(1) К(2) К(3) К(4) К(5) К(6) К(7) К(8) K(9)

12 5 4 3 1 9 8 6 7.

Первоначально Н принимается равным 4. Исходная последовательность разбивается на следующие четыре части:

K(1) K(5) K(9)│K(2) K(6)│K(3) K(7)│K(4) K(8)

12 1 7 │ 5 9 │ 4 8 │ 3 6.

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

К(1) К(2) К(3) К(4) К(5) К(6) К(7) К(8) K(9)

1 5 4 3 7 9 8 6 12.

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

K(1) K(3) K(5) K(7) K(9) │ К(2) К(4) К(6) К(8)

1 4 7 8 12 │ 5 3 9 6.

После упорядочения элементов внутри этих последовательностей набор данных будет иметь следующий вид:

К(1) К(2) К(3) К(4) К(5) К(6) К(7) К(8) K(9)

1 3 4 5 7 6 8 9 12.

Затем снова H сокращается вдвое и становится равным 1. При этом полученная последовательность сортируется обычной вставкой

К(1) К(2) К(3) К(4) К(5) К(6) К(7) К(8) K(9)

1 3 4 5 6 7 8 9 12.

1.2.5. Сортировка слиянием

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

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

Структурограмма алгоритма сортировки слиянием в массив C(N+M) двух массивов A(N) и B(M) имеет вид, представленный на рис. 7.

Данный метод можно использовать для сортировки одного

файла следующим образом. Файл разделяется на N частей размером в один элемент, и объединяются соседние (необъединенные) пары элементов. В результате образуются примерно N/2 частей размером в два элемента. Данный процесс продолжается, пока не останется только одна последовательность размером N.

Ниже показано, как выполняется этот процесс на последовательности примера. Каждая отдельная часть на рисунке заключена в скобки.

Исходный файл: [25] [57] [48] [37] [12] [92] [86] [33]

Просмотр 1 : [25 57] [37 48] [12 92] [33 86]

Просмотр 2 : [25 37 48 57] [12 33 86 92]

Просмотр 3 : [12 25 33 37 48 57 86 92].

Источник: http://www.metods-rgrtu.ru/index.php/mets-3600-3699/112-3678?start=3

Большая Энциклопедия Нефти и Газа

Cтраница 1

Обменная сортировка некоторым систематическим образом меняет местами пары имен, не отвечающие порядку до тех пор, пока такие пары существуют. [1]

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

Разновидностьобменной сортировки, предложенная Лоаром. В соответствии с алгоритмом быстрой сортировки вначале определяются первый и последний элементы массива.

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

После этого та же самая процедура применяется к двум полученным частям и так до образования частей, содержащих всего по одному элементу. [3]

Ьитчира (обменная сортировка слиянием) Бид сортировки ( S. [4]

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

Пояснения к обменной сортировке. [6]

Таким образом, обменная сортировка существенно использует любую уже имеющуюся упорядоченность в таблице. [7]

Такой анализ показывает, чтообменная сортировка и ее небольшие усовершенствования представляют собой нечто среднее между сортировками с помощью включений и с помощью выбора. Шейкер-ная же сортировка с успехом используется в тех случаях, когда известно, что элементы почти упорядочены – на практике это бывает весьма редко. [8]

Мы рассмотрим один простейших методовобменной сортировки – так называемый метод пузырька. Он называется так потому, что в результате этой сортировки записи с меньшими ключами опускаются на дно, а записи с большими ключами – всплывают, как пузыри. [9]

Для пояснения заметим, что упомянутаяобменная сортировка прекращает работу, если на очередном просмотре состояние сортируемого массива не изменилось. Укажите соответствие указанных методов и свойств. [10]

Каждый программист знаком с некоторым вариантомобменной сортировки. [11]

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

Поразрядная сортировка группированием эффективна с точки зрения времени выполнения, но требует чрезмерно большой памяти, так что она редко используется на вычислительных машинах; для сортировки перфокарт, где проблема места не возникает, это хороший метод сортировки. [12]

В этом разделе мы обсуждаем два типаобменных сортировок: хорошо известную, но относительно неэффективную пузырьковую сортировку и быструю сортировку – один из лучших со всех точек зрения алгоритмов внутренней сортировки. [13]

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

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

Страницы: 1 2

Источник: http://www.ngpedia.ru/id459243p1.html

Сортировка обменом («пузырьковая сортировка»)

⇐ ПредыдущаяСтр 8 из 17Следующая ⇒

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

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

Всего требуется n-1 проход.

1 шаг:

3 11

7 11 2 11 9 11

2 шаг: 1 11 4 11

3 5 1 7

4 7

3 шаг: 2 7

1 5

4 5

4 шаг: 2 5

1 3 2 4

5 шаг:

2 3

6 шаг:

7 шаг:

Результат:

БЛОК – СХЕМА

Æ 1

1 Æ

R = A(K-1) A(K-1)=A(K) A(K) = R

Программа реализирующая метод обмена («пузырька»), будет иметь следующий вид:

Program Duddle Sort;

Uses Crt;

Const

N = 20; { длина массива}

Type

TVector = array [1…n] of Real;

Var

Vector : Tvector;

B : Real;

i, K : Integer;

begin

ClrScr;

Writeln (‘введите элементы массива:’);

for i: = 1 to n do Read (Vector [i]); Readln;

{- – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – }

for K: = n downto 2 do

{“всплывание” очередного максимального элемента}

{на К-ю позицию}

for i: = 1 to K-1 do

if Vector [i] > Vector [i+1] then

begin

B: = Vector [i];

Vector [i]: = Vector [i+1];

Vector [i+1]: = B;

End;

{- – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – }

Writeln (‘отсортированный массив:’);

For i: = 1 to n do Write (‘Vector [i]: 8 : 2’);

Writeln;

End.

Результат работы:

Bведите элементы массива: Отсортированный массив:

Сортировка фон Неймана (слиянием)

Заданы два упорядоченных по возрастанию элементов одномерных массива: а размерности n и b размерности m. Требуется получить третий массив с размерности n+m, который содержал бы все элементы исходных массивов, упорядоченных по возрастанию.

Алгоритм решения этой задачи известен как «сортировка фон Неймана» или сортировка слиянием. Идея алгоритма состоит в следующем. Сначала анализируются первые элементы обоих массивов. Меньший элемент переписывается в новый массив.

Оставшийся элемент последовательно сравнивается с элементами из другого массива. В новый массив после каждого сравнения попадает меньший элемент. Процесс продолжается до исчерпания элементов одного из массивов. Затем остаток другого массива дописывается в новый массив.

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

Программа, реализующая метод Фон-Неймана, имеет следующий вид:

БЛОК – СХЕМА

Æ 1

1 Æ

[(K)=A(I)] I = I+1 K = K+1

[(K)=B(J)] J = J+1 K = K+1

[(K)=A(I)] I = I+1 K = K+1

program confluence;

const n = 10;

m = 20;

l = n + m;

var x: array [1..n] of integer;

y: array [1..m] of integer;

z: array [1..l] of integer;

k, i, j: integer;

begin

for i: = 1 to n do

read (x[i]); {формирование первого упорядоченного массива}

for i: = 1 to m do

read (y[i]); {формирование второго упорядоченного массива}

I:= 1; j:=1; l:=1 {i-индекс первого массива, j-индекс второго

массива, l-индекс результирующего массива}

while (i

Источник: https://lektsia.com/1×340.html

Сортировка массиав | Programmirovanie-dla-sсhool

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

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

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

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

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

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

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

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

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

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

Решение

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

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

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

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

Procedure sorting1(var a:myarray); {Сортировка по возрастанию методом простого выбора} var i,j:integer; k,m:integer; {номер и значение максимального элемента} begin for i:= n downto 2 do{задаем длину рассматриваемой части массива} begin {ищем максимальный элемент и его номер} k:=i; m:=a[i]; for j:= 1 to i-1 do if a[j] > m then begin k:=j; m:=a[k] end; {меняем местами найденный элемент и последний} if k i then begin a[k]:=a[i]; a[i]:= m; end; end; end; end;

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

program primer_1;const n = 10; type myarray = array[1..n] of integer; var a:myarray; Procedure sorting1(var a:myarray); {Линейная сортировка (сортировка отбором)} … begin {main} writeln('Введите исходный массив:'); for i:=1 to n do read(a[i]); sorting1(a); writeln('Отсортированный массив:'); for i:=1 to 10 do write(a[i],' '); writeln; end.

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

Номер элемента	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

При упорядочивании массива по убыванию необходимо перемещать минимальный элемент. Для чего в алгоритме нахождения максимального элемента достаточно знак “>” поменять на знак “ a[i+1] then begin t:=a[i]; a[i]:=a[i+1]; a[i+1]:=t; end; end;

Для упорядочения элементов массива по убыванию их значений необходимо при сравнении элементов массива знак “>” заменить на “

Источник: http://gospodaretsva.com/urok-28-sortirovka-massiva.html

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

Источник: https://infopedia.su/17×5354.html

prerek.ru

с. 1

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

Одним из наиболее известных алгоритмов сортировки является метод пузырька (или пузырьковый метод). Его популярность объясняется как запоминающимся названием, так и простотой алгоритма.

Однако, эта сортировка является одной из самых худших среди всех когда-либо придуманных алгоритмов сортировки.

Пузырьковая сортировка относится к методам обменной сортировки.

Она основана на выполнении в цикле операций сравнения и при необходимости обмена соседних элементов.

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

{сортировка пузырьковым методом}

procedure Bubble;

var

i,j: index;

x: item;

begin

for i := 2 to n do

begin

for j := n downto i do

if a[j-1].key> a[j].key then

begin

x := a[j-1];

a[j-1] := a[j];

a[j] := x;

end;

end; {конец сортировки пузырьковым методом}

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

Для иллюстрации работы сортировки пузырьковым методом в таблице 2.2.1 даны результаты каждого этапа сортировки массива (38, 52, 17, 36, 98, 21, 12, 74).

Таблица 2.2.1

Сортировка с помощью прямого обмена (пузырьковая сортировка) Оба разбиравшихся до этого метода можно тоже рассматривать как “обменные” сортировки. В данном же, однако, разделе описан метод, где обмен местами двух элементов представляет собой характернейшую особенность процесса. Изложенный ниже алгоритм прямого обмена основывается на сравнении и смене мест для пары соседних элементов и продолжении этого процесса до тех пор, пока не будут упорядочены все элементы. Как и в упоминавшемся методе прямого выбора, мы повторяем проходы по массиву, сдвигая каждый раз наименьший элемент оставшейся последовательности к левому концу массива. Если мы будем рассматривать массивы как вертикальные, а не горизонтальные построения, то элементы можно интерпретировать как пузырьки в чане с водой, причем вес каждого соответствует его ключу. В этом случае при каждом проходе один пузырек как бы поднимается до уровня, соответствующего его весу (см. иллюстрацию на рисунке ниже). Такой метод широко известен под именем “пузырьковая сортировка”. Алгоритм метода прямого обмена for i = 2 to n for j = n to i step -1 if a(j) < a(j - 1) then x = a(j – 1) a(j – 1) = a(j) a(j) = x endif next j next i return В нашем случае получился один проход “вхолостую”. Чтобы лишний раз не просматривать элементы, а значит проводить сравнения, затрачивая на это время, можно ввести флажок fl, который остается в значении false, если при очередном проходе не будет произведено ни одного обмена. На нижеприведенном алгоритме добавления отмечены жирным шрифтом. fl = true for i = 2 to n if fl = false then return Endif fl = false for j = n to i step -1 if a(j) < a(j - 1) then fl = true x = a(j – 1) a(j – 1) = a(j) a(j) = x endif next j next i return Если массив уже отсортирован и применяется алгоритм с флажком, то достаточно всего одного прохода, и тогда получаем минимальное число сравнений Улучшением пузырькового метода является шейкерная сортировка, где после каждого прохода меняют направление во внутреннем цикле. Эффективность алгоритма сортировки прямым обменом Число сравнений Cmax = n(n-1)/2 , порядок О(n2). Число перемещений Мmax=3Cmax=3n(n-1)/2, порядок О(n2). Если массив уже отсортирован и применяется алгоритм с флажком, то достаточно всего одного прохода, и тогда получаем минимальное число сравнений Cmin = n – 1, порядок О(n), а перемещения вообще отсутствуют Сравнительный анализ прямых методов сортировок показывает, что обменная “сортировка” в классическом виде представляет собой нечто среднее между сортировками с помощью включений и с помощью выбора. Если же в нее внесены приведенные выше усовершенствования, то для достаточно упорядоченных массивов пузырьковая сортировка даже имеет преимущество. Быстрая сортировка. Относится к методам обменной сортировки. В основе лежит методика разделения ключей по отношению к выбранному. Слева от 6 располагают все ключи с меньшими, а справа – с большими или равными 6. Алгоритм быстрой сортировки Sub Sort (L, R) i = L j = R x = a((L + R) div 2) repeat while a(i) < x do i = i + 1 endwhile while a(j) > x do j = j – 1 endwhile if i j if L < j then sort (L, j) endif if i < R then sort (i, R) endif return Sub QuickSort Sort (1, n) return Из всех существующих методов сортировки Quick Sort самый эффективный. Его эффективность имеет порядок О(n log2 n) Сортировка Шелла. К улучшенным методам сортировки относятся: Сортировка Шелла (сортировка с уменьшающимся шагом) Быстрая сортировка (Quick Sort) В 1959 году Д. Шеллом было предложено усовершенствование сортировки с помощью метода прямого включения. Иллюстрация его сортировки с начальным шагом, равным 4, представлена на нижеследующем рисунке. Сначала отдельно группируются и в группах сортируются элементы, отстоящие друг от друга на расстоянии 4. Такой процесс называется четверной сортировкой. В нашем примере 8 элементов, и каждая группа состоит из двух элементов, то есть 1-й и 5-й элементы, 2-й и 6-й, 3-й и 7-й и, наконец, 4-й и 8-й элементы. После четверной сортировки элементы перегруппировываются – теперь каждый элемент группы отстоит от другого на 2 позиции – и вновь сортируются. Это называется двойной сортировкой. И наконец, на третьем проходе идет обычная или одинарная сортировка. На первый взгляд можно засомневаться: если необходимо несколько процессов сортировки, причем в каждый включаются все элементы, то не добавят ли они больше работы, чем сэкономят? Однако, на каждом этапе либо сортируется относительно мало элементов, либо элементы уже довольно хорошо упорядочены и требуют сравнительно немного перестановок. Ясно, что такой метод в результате дает упорядоченный массив, и, конечно, сразу же видно, что каждый проход от предыдущих только выигрывает; также очевидно, что расстояния в группах можно уменьшать по разному, лишь бы последнее было единичным, ведь в самом плохом случае последний проход и сделает всю работу. Приводимый ниже алгоритм не ориентирован на некую определенную последовательность расстояний и использует метод прямой вставки с условным переходом. При использовании метода барьера каждая из сортировок нуждается в постановке своего собственного барьера, поэтому приходится расширять массив с [0..n ] до [-h1..n ]. Не доказано, какие расстояния дают наилучший результат, но они не должны быть множителями один другого. Д. Кнут предлагает такую последовательность шагов h (в обратном порядке): 1, 3, 7, 15, 31, … То есть: h m =2h m-1+1 а количество шагов t = log2n – 1. При такой организации алгоритма его эффективность имеет порядок O ( n1.5) Алгоритм сортировки Шелла Обозначим h[1..t] – массив размеров шагов a[1..n] – сортируемый массив k – шаг сортировки x – значение вставляемого элемента ShellSort const t = 3 h(1) = 7 h(2) = 3 h(3) = 1 for m = 1 to t k = h(m) for i = 1 + k to n x = a(i) for j = i – k to 1 step -k if x < a(j) then a( j+k) = a(j) else goto L endif next j L: a(j+k) = x next i next m return
Исходное состояние	Первый проход	Второй проход	Третий проход	Четвертый проход	Пятый проход	Шестой проход	Седьмой проход
38	12	12	12	12	12	12	12
52	38	17	17	17	17	17	17
17	52	38	21	21	21	21	21
36	17	52	38	36	36	36	36
98	36	21	52	38	38	38	38
21	98	36	36	52	52	52	52
12	21	98	74	74	74	74	74
74	74	74	98	98	98	98	98

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

Это означает, что при сортировке пузырьковым методом всегда выполняется (n2-n)/2 операций сравнения, где «n» задает число сортируемых элементов массива. Эта формула выводится на том основании, что внешний цикл сортировки пузырьковым методом выполняется n-1 раз, а внутренний цикл выполняется n/2 раз.

Их перемножение даст указанную формулу.

Число операций обмена будет нулевым для наилучшего случая, когда исходный массив уже является отсортированным. Число операций обмена для среднего случая будет равно 3(n2-n)/4, а для наихудшего случая будет равно 3(n2-n)/2 раз.

Читайте также: Уф лампы

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

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

Нетрудно заметить, что существует неприятная асимметрия – один «легкий пузырек», расположенный внизу массива, «всплывает» на свое место за один проход, а «тяжелый пузырек», расположенный наверху, «опускается» на свое место только на один шаг за проход.

Так для сортировки массива (12, 18, 42, 44, 55, 67, 94, 06) потребуется один проход, а для массива (94, 06, 12, 18, 42, 44, 55, 67) таких проходов потребуется семь! Между тем, в обоих массивах в начальном состоянии всего по одному «неупорядоченному» элементу.

Однако расположенный не на своем месте в конце первого массива элемент «06» достигает своего места за один проход, а элемент «94» очень медленно достигает своего места.

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

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

{челночная сортировка}

procedure Shaker;

var

j, k, l, r: index;

x: item;

begin

l := 2; r := n; k := n;

repeat

for j := r downto l do

if a[j-1].key > a[j].key then

begin

x := a[j-1];

a[j-1] := a[j];

a[j] := x;

k := j;

end;

l := k+1;

for j := l to r do

if a[j-1].key > a[j].key then

begin

x := a[j-1];

a[j-1] := a[j];

a[j] := x;

k := j;

end;

r := k-1;

until l>r

end; { конец челночной сортировки }

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

с. 1

Кислород. Физические и химические свойства кислорода

Источник: http://prerek.ru/safia/sortirovka-prostim-obmenom/main.html

Пузырьковая сортировка и все-все-все

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

Но сегодня речь пойдёт не про quick sort, а про другой обменный способ – старую добрую пузырьковую сортировку и её улучшения, модификации, мутации и разновидности. Практический выхлоп от данных методов не ахти какой и многие хабрапользователи всё это проходили ещё в первом классе.

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

image: пузырьки

Сегодня поговорим о простейших сортировках обменами.

Если кому интересно, скажу, что есть и другие классы – сортировки выбором, сортировки вставками, сортировки слиянием, сортировки распределением, гибридные сортировки и параллельные сортировки. Есть, кстати, ещё эзотерические сортировки. Это различные фейковые, принципиально нереализуемые, шуточные и прочие псевдо-алгоритмы, про которые я в хабе «IT-юмор» как-нибудь напишу пару статей.

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

Заранее предупрежу, что почти все приведённые способы весьма медленные и глубокого анализа их временной сложности не будет.

Какие-то побыстрее, какие-то помедленнее, но, грубо говоря, можно сказать, что в среднем O(n2). Также я не вижу резона загромождать статью реализациями на каких-либо языках программирования.

Заинтересовавшиеся без малейшего труда смогут найти примеры кода на Розетте, в Википедии или где-нибудь ещё.

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

Если сравниваемые элементы не отсортированы друг относительно друга – то меняем их местами. Вопрос только в том, каким именно макаром массив обходить и по какому принципу выбирать пары для сравнения.

Начнём не с эталонной пузырьковой сортировки, а с алгоритма, который называется…

Глупая сортировка

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

Снова проходим-проверяем массив, если встретили снова «неправильную» пару соседних элементов, то меняем местами и опять начинаем всё сызнова. Продолжаем до тех пор пока массив потихоньку-полегоньку не отсортируется.

«Так любой дурак сортировать умеет» — скажете Вы и будете абсолютно правы.

Именно поэтому сортировку и прозвали «глупой». На этой лекции мы будем последовательно совершенствовать и видоизменять данный способ.

Сейчас у него временная сложность O(n3), произведя одну коррекцию, мы уже доведём до O(n2), потом ускорим ещё немного, потом ещё, а в конце концов мы получим O(n log n) – и это будет вовсе не «Быстрая сортировка»!

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

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

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

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

Если не только в конец задвигать максимумы, а ещё и в начало перебрасывать минимумы то у нас получается…

Шейкерная сортировка

Она же сортировка перемешиванием, она же коктейльная сортировка. Начинается процесс как в «пузырьке»: выдавливаем максимум на самые задворки.

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

Шейкерная сортировка работает немного быстрее чем пузырьковая, поскольку по массиву в нужных направлениях попеременно мигрируют и максимумы и минимумы. Улучшения, как говорится, налицо.

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

Чётно-нечётная сортировка

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

Затем наоборот – «чётные по счёту» элементы сравниваем/меняем с «нечётными». Затем снова «нечёт-чёт», потом опять «чёт-нечет». Процесс останавливается тогда, когда после подряд двух проходов по массиву («нечётно-чётному» и «чётно-нечётному») не произошло ни одного обмена. Стало быть, отсортировали.

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

Разберём последнее покращення* для Сортування бульбашкою** — Сортування гребінцем***. Этот способ упорядочивает весьма шустро, O(n2) – его наихудшая сложность. В среднем по времени имеем O(n log n), а лучшая даже, не поверите, O(n).

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

Во всём виноваты черепашки

Небольшая предыстория. В 1980 году Влодзимеж Добосиевич пояснил почему пузырьковая и производные от неё сортировки работают так медленно. Это всё из-за черепашек. «Черепахи» — небольшие по значению элементы, которые находятся в конце списка.

Как Вы, возможно, заметили пузырьковые сортировки ориентированы на «кроликов» (не путать с «кроликами» Бабушкина) – больших по значению элементов в начале списка. Они весьма резво перемещаются к финишу. А вот медлительные пресмыкающиеся на старт ползут неохотно.

Подгонять «тортилл» можно с помощью расчёски.

image: виноватая черепашка

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

В «пузырьке», «шейкере» и «чёт-нечете» при переборе массива сравниваются соседние элементы. Основная идея «расчёски» в том, чтобы первоначально брать достаточно большое расстояние между сравниваемыми элементами и по мере упорядочивания массива сужать это расстояние вплоть до минимального.

Таким образом мы как бы причёсываем массив, постепенно разглаживая на всё более аккуратные пряди.

Первоначальный разрыв между сравниваемыми элементами лучше брать не абы какой, а с учётом специальной величины называемой фактором уменьшения, оптимальное значение которой равно примерно 1,247.

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

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

Опытным и теоретическим путём установлено оптимальное значение фактора уменьшения:

Когда был изобретён этот метод, на него на стыке 70-х и 80-х мало кто обратил внимание.

Десятилетие спустя, когда программирование перестало быть уделом учёных и инженеров IBM, а уже лавинообразно набирало массовый характер, способ переоткрыли, исследовали и популяризировали в 1991 году Стивен Лейси и Ричард Бокс. Вот собственно и всё что я хотел Вам рассказать про пузырьковую сортировку и иже с ней.

— Примечания

* покращення (укр.) – улучшение

** Сортування бульбашкою (укр.) – Сортировка пузырьком
*** Сортування гребінцем (укр.) – Сортировка расчёской

Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.

57.1%Глупая сортировка772
91.2%Пузырьковая сортировка1234
39.7%Шейкерная сортировка538
15.4%Чётно-нечётная сортировка209
17%Сортировка расчёской231

Источник: https://habr.com/post/204600/

Сортировка методом пузырька

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

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

Как известно воздух легче воды, поэтому пузырьки воздуха всплывают. Это просто аналогия. В сортировке методом пузырька по возрастанию более легкие (с меньшим значением) элементы постепенно “всплывают” в начало массива, а более тяжелые друг за другом опускаются на дно (в конец массива).

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

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

Остальная часть массива остается не отсортированной, хотя некоторое перемещение элементов с меньшим значением в начало массива наблюдается.
При втором проходе незачем сравнивать последний элемент с предпоследним. Последний элемент уже стоит на своем месте. Значит, число сравнений будет на одно меньше.
На третьем проходе уже не надо сравнивать предпоследний и третий элемент с конца. Поэтому число сравнений будет на два меньше, чем при первом проходе.
В конце концов, при проходе по массиву, когда остаются только два элемента, которые надо сравнить, выполняется только одно сравнение.
После этого первый элемент не с чем сравнивать, и, следовательно, последний проход по массиву не нужен. Другими словами, количество проходов по массиву равно m-1, где m – это количество элементов массива.
Количество сравнений в каждом проходе равно m-i, где i – это номер прохода по массиву (первый, второй, третий и т.д.).
При обмене элементов массива обычно используется “буферная” (третья) переменная, куда временно помещается значение одного из элементов.

Программа на языке Паскаль:

const m = 10;

var arr: array[1..m] of integer; i, j, k: integer;

begin randomize;
write ('Исходный массив: '); for i := 1 to m do begin arr[i] := random(256); write (arr[i]:4); end; writeln; writeln;

for i := 1 to m-1 do for j := 1 to m-i do if arr[j] > arr[j+1] then begin k := arr[j]; arr[j] := arr[j+1]; arr[j+1] := k end;
write ('Отсортированный массив: '); for i := 1 to m do write (arr[i]:4);
writeln;

readln
end.

Источник: https://pas1.ru/bubbles