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

Введение

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

Сортировка слиянием (Merge sort)

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

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

Подробный разбор пузырьковой сортировки

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

Первая итереация (первый повтор алгоритма) меняет между собой 4 и 2 так как цифра два меньше чем четыре 2<4, повторюсь что алгоритм меняет значения между собой если, слева оно меньше чем справа. Далее происходит сверка между 4 и 3, и так как 3 меньше чем 4 (3<4) происходит обмен значениями. Потом проходит проверку между 4 и 8 и так как значение 4 меньше чем 8 то не происходит обмена, ведь уже и так всё на своих местах.

Далее сравнивается 8 и 1 и так как 1 меньше чем 8 (1<8) и оно не находиться слева то происходит обмен значениями.После это первый повтор алгоритма заканчивается, на анимации я выделил это зеленым фоном.

В итоге по окончанию работы алгоритма пузырьковой сортировки мы имеем следующий порядок числового массива: 2 3 4 1 8

и начинается второй повтор алгоритма.

Далее сравнивается 2 и 3 и так как два меньше чем три и оно находиться слева то просто идем дальше ничего не трогая. Также проверяем и 3 и 4 и тоже самое условие выполняется 3<4 и оно слева. Дальше проверяется 4 и 1 и тут мы видим что число 1<4 и не находиться слева, поэтому алгоритм меняет их местами. В крайний раз для второго повторения алгоритма проверяется 4 и 8, но тут всё в порядке, и мы дошли до конца начинаем третье повторение. Итоги для второго повторения такие : 2 3 1 4 8

Третье повторение пузырькового алгоритма начинается с сравнения 2 и 3, тут алгоритм проверяет что 2<3 и 2 находиться слева и оставляет их в покое и идет дальше. Сравнение же 3 и 1 показывает что 1 то меньше чем три, но почему то не слева и меняет их местами. Далее идет сравнение 3 и 4, тут всё в порядке и так далее до сравнения 4 и 8.

После этого получается следующий результат: 2 1 3 4 8

Как мы видим почти все цифры уже на своих местах и в порядке возрастания! Осталось только в последнем повторении пузырькового алгоритма поменять местами 2 и 1 и всё. После того как алгоритм закончил свою работу и проверил что цифры больше нельзя поменять местами он перестает работать с таким вот результатом: 1 2 3 4 8

2. Обзор алгоритмов сортировки

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

Рассмотрим алгоритмы сортировки «на месте», то есть те алгоритмы в которых не используется копирование массива.

Удобной мерой эффективности алгоритмов сортировки «на месте» является число необходимых сравнений в ходе сортировки и число необходимых пересылок элементов.

Эффективные алгоритмы сортировки требуют порядка

сравнений, где N — число элементов, а С — число необходимых сравнений.

Мы рассмотрим простые методы сортировки, которые требуют число сравнений порядка

Методы сортировки «на месте» можно разбить на три основных класса:

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

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

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

В сортировке выбором выбирается элемент с наибольшим значением ключа и меняется местами с последним. Затем то же самое повторяется для s-1 элемента. Найденный элемент с наибольшим значением ключа меняется

Рисунок 1. Сортировка простым выбором

В сортировке включениями элементы разделяются на уже упорядоченную и неупорядоченную последовательности. В начале упорядоченная часть содержит только один элемент. Очередной элемент из начала неупорядоченной части вставляется на подходящее место в упорядоченную часть. При этом упорядоченная часть удлиняется на один элемент, а неупорядоченная — укорачивается. Сортировка заканчивается при исчезновении неупорядоченной части (рисунок 2).

Рисунок 2. Сортировка простыми включениями

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

Рисунок 3. Сортировка простым обменом

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

Например:

сортировка вставками;

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

корневая сортировка;

пирамидальная сортировка;

сортировка слиянием;

быстрая сортировка;

сортировка Шелла и др.

Рассмотрим подробнее основные типы и виды сортировок (сначала простые сортировки затем более сложные).

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

Метод основан на следующем правиле:

Выбирается элемент с наибольшим значением ключа

Он меняется местами с последним элементом arr . Затем эти операции повторяются с оставшимися первыми s-1 элементами, затем — с s-2 первыми элементами и т.д. до тех пор, пока не останется только первый элемент — наименьший. Пример сортировки методом простого выбора показан на рисунке 4:

Рисунок 4. Сортировка массива простым выбором

Эффективность сортировки простым выбором. Число сравнений ключей не зависит от начального порядка ключей. Операция сравнения выполняется в теле цикла с управляющей переменной k

и средним числом повторений size/2. Этот цикл, в свою очередь, находится в теле цикла с управляющей переменной L

и числом повторений size −1. Таким образом, число сравнений

С= (size −1) * size −1/2

Число пересылок, напротив, зависит от начального порядка ключей. Если принять, что операция сравнения в теле цикла по k

дает результат «истина» в половине случаев, то среднее число пересылок в этом цикле равно size/4. Цикл по L

, как указывалось выше, выполняется size −1 раз и в теле цикла выполняется три пересылки и цикл по k

. С учетом этого число пересылок:

М= (3+ size/4) * (size −1)

Получаем, что при сортировке простым выбором и число сравнений, и число пересылок пропорционально .

Метод пузырька

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

В общем случае алгоритм сортировки пузырьком следующий:

1. Сравнить текущий элемент со следующим.
2. Если следующий элемент меньше/больше текущего, поменять их местами.
3. Если массив отсортирован, закончить алгоритм, иначе перейти на шаг 1.

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

Внешний цикл в худшем случае совершает N (кол-во элементов) – 1 проходов, то есть внутренний цикл выполняется N-1 раз.

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

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

2.7 Общий анализ приведенных сортировок

Приведем выводы по простым методам сортировки:

Время сортировки пропорционально квадрату размерности массива

Более точные оценки производительности простых методов сортировки показывают, что наиболее быстрой

является сортировка вставками, а наиболее медленной

− сортировка обменом.

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

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

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

Сравним простые и сложные методы сортировки по производительности:

Таблица 1. Сравнительные показатели производительности различных методов сортировки массивов

Простые методы сортировки
Метод сортировки	Время сортировки для размера 256, миллисекунд	Время сортировки для размера 512, миллисекунд	Соотношение методов по производительности (относительное время сортировки)
Вставками (метод простых вставок)	356	1444	1
Выбором	509	1956	1.3
Обменом (пузырек)	1026	4054	3
Сложные методы сортировки
Обменом (Хоора)	60	116	1
Выбором (с помощью двоичного дерева	110	241	1.7
Вставками (Шелла)	127	349	2.1

Из приведенных в таблице данных следует, в частности, для относительно небольшого массива в 512 элементов:

Худшая по производительности из простых сортировок (сортировка обменом) работает в 35 раз медленнее быстрой сортировки Хоора.

Самая быстрая из простых сортировок (простая сортировка вставками) работает медленнее в 4.2 раза чем худшая по производительности из сложных сортировок (сортировка Шелла).

При увеличении размера массива указанные выше эффекты проявляются в большей степени

Использовать

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

Обратите внимание, что сначала сортируется самый большой конец, а меньшим элементам требуется больше времени, чтобы переместиться в правильное положение.

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

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

Жаргон Файл , который лихо звонков bogosort «архетипический извращенно ужасный алгоритм», также вызывает пузырьковую сортировку «общий плохой алгоритм». Дональд Кнут в своей книге «Искусство компьютерного программирования» пришел к выводу, что «пузырьковой сортировке, похоже, нечего рекомендовать, кроме броского названия и того факта, что она приводит к некоторым интересным теоретическим проблемам», некоторые из которых он затем обсуждает.

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

Пузырьковая сортировка также плохо взаимодействует с современным оборудованием ЦП. Он производит как минимум вдвое больше записей, чем сортировка вставкой, вдвое больше промахов в кеш и асимптотически больше ошибочных прогнозов переходов . Эксперименты с сортировкой строк Astrachan в Java показывают, что пузырьковая сортировка примерно в пять раз быстрее сортировки вставкой и на 70% быстрее сортировки по выбору .

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

Изменение фотографии профиля

Как улучшить пузырьковую сортировку

Ниже вы можете видеть оптимизированную версию пузырьковой сортировки.

for (int i = 0; i < 10; i++) {
bool flag = true;
for (int j = 0; j < 10 — (i + 1); j++) {
if (digitals > digitals) {
flag = false;
swap (digitals, digitals);
}
}
if (flag) {
break;
}
}

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

for(inti=;i<10;i++){ boolflag=true; for(intj=;j<10-(i+1);j++){ if(digitalsj>digitalsj+1){ flag=false; swap(digitalsj,digitalsj+1); } } if(flag){ break; } }

Давайте посмотрим, что мы сделали для ее оптимизации:

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

Для этого в строке 5: чтобы пузырьковая сортировка останавливалась (когда массив уже стал отсортирован), мы объявили булеву переменную (ее обычно называют флаг или флажок). Еще при ее инициализации мы поместили значение , но она меняется на:

false, если результат условия в строке 4: положительный.

А в строке 9: чтобы мы могли выйти из алгоритма мы проверяем:

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

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

int b = digitals;
digitals = digitals;
digitals = b;

1 2 3

intb=digitalsj; digitalsj=digitalsj+1; digitalsj+1=b;

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

Метод пузырьковой сортировки в Паскале

Замечание 1

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

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

1. Для выполнения процесса сортировки применяются два цикла, причём один цикл вложен в другой. Первый цикл применяется для формирования шагов, второй — под-шагов.

2. Основой алгоритма является сравнение двух элементов. К примеру, есть массив с десятью элементами. Элементы подлежат сравнению парами: 1 и 2, 2 и 3, 3 и 4 ,4 и 5 ,6 и 7 и так далее. Если при выполнении сравнения текущий элемент больше по величине чем следующий, то они меняются местами. К примеру, если первый элемент пять, а второй два, то они меняются местами.

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

Приведём наглядный пример. Имеется массив, включающий в себя семь элементов: 2, 5, 11, 1, 7, 8, 3. Процесс сортировки изображён на рисунке 1.

Рисунок 1. Процесс сортировки. Автор24 — интернет-биржа студенческих работ

Далее сформируем собственно программу, реализующую данный алгоритм на языке Паскаль. Ниже приведён текст программы:

Замечание 2

Следует подчеркнуть, что элемент k нужен только для того, чтобы выполнить обмен местами двух элементов. Это объясняется тем, что Паскаль не имеет команды, которая смогла бы осуществить эту операцию. Это вынуждает формировать данную процедуру программным путём, вводя добавочный элемент для обмена.

Таблица 2: Сортировка пузырьком в многопоточном режиме

1	2	3	4	5	6	7	8	9	10	11	12	13	14
1	2	3	4	5	6	7	8	9	10	11	12	13	14
1	2	3	4	5	6	7	8	9	10	11	12	13	14
1	2	3	4	5	6	7	8	9	10	11	12	13	14
1	2	3	4	5	6	7	8	9	10	11	12	13	14
2	1	3	4	5	6	7	8	9	10	11	12	13	14
2	3	1	4	5	6	7	8	9	10	11	12	13	14
3	2	4	1	5	6	7	8	9	10	11	12	13	14
3	4	2	5	1	6	7	8	9	10	11	12	13	14
4	3	5	2	6	1	7	8	9	10	11	12	13	14
4	5	3	6	2	7	1	8	9	10	11	12	13	14
5	4	6	3	7	2	8	1	9	10	11	12	13	14
5	6	4	7	3	8	2	9	1	10	11	12	13	14
6	5	7	4	8	3	9	2	10	1	11	12	13	14
6	7	5	8	4	9	3	10	2	11	1	12	13	14
7	6	8	5	9	4	10	3	11	2	12	1	13	14
7	8	6	9	5	10	4	11	3	12	2	13	1	14
8	7	9	6	10	5	11	4	12	3	13	2	14	1
8	9	7	10	6	11	5	12	4	13	3	14	2	1
9	8	10	7	11	6	12	5	13	4	14	3	2	1
9	10	8	11	7	12	6	13	5	14	4	3	2	1
10	9	11	8	12	7	13	6	14	5	4	3	2	1
10	11	9	12	8	13	7	14	6	5	4	3	2	1
11	10	12	9	13	8	14	7	6	5	4	3	2	1
11	12	10	13	9	14	8	7	6	5	4	3	2	1
12	11	13	10	14	9	8	7	6	5	4	3	2	1
12	13	11	14	10	9	8	7	6	5	4	3	2	1
13	12	14	11	10	9	8	7	6	5	4	3	2	1
13	14	12	11	10	9	8	7	6	5	4	3	2	1
14	13	12	11	10	9	8	7	6	5	4	3	2	1
14	13	12	11	10	9	8	7	6	5	4	3	2	1

Анализ

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

Производительность

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

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

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

Кролики и черепахи

Расстояние и направление, в котором элементы должны перемещаться во время сортировки, определяют производительность пузырьковой сортировки, поскольку элементы перемещаются в разных направлениях с разной скоростью. Элемент, который должен переместиться в конец списка, может перемещаться быстро, потому что он может принимать участие в последовательных заменах. Например, самый большой элемент в списке будет выигрывать при каждом обмене, поэтому он перемещается в свою отсортированную позицию на первом проходе, даже если он начинается с начала. С другой стороны, элемент, который должен двигаться к началу списка, не может перемещаться быстрее, чем один шаг за проход, поэтому элементы перемещаются к началу очень медленно. Если наименьший элемент находится в конце списка, потребуется n -1 проход, чтобы переместить его в начало. Это привело к тому, что эти типы элементов были названы кроликами и черепахами соответственно в честь персонажей басни Эзопа о Черепахе и Зайце .

Были предприняты различные усилия по устранению черепах, чтобы повысить скорость сортировки пузырей. Сортировка коктейлей — это двунаправленная сортировка пузырьков, которая идет от начала до конца, а затем меняет свое направление, идя от конца к началу. Он может довольно хорошо перемещать черепах, но сохраняет сложность наихудшего случая O (n 2 ) . Комбинированная сортировка сравнивает элементы, разделенные большими промежутками, и может очень быстро перемещать черепах, прежде чем переходить к все меньшим и меньшим промежуткам для сглаживания списка. Его средняя скорость сопоставима с более быстрыми алгоритмами вроде быстрой сортировки .

Пошаговый пример

Возьмите массив чисел «5 1 4 2 8» и отсортируйте его от наименьшего числа к наибольшему с помощью пузырьковой сортировки. На каждом этапе сравниваются элементы, выделенные жирным шрифтом . Потребуется три прохода;

Первый проход

( 5 1 4 2 8) → ( 1 5 4 2 8). Здесь алгоритм сравнивает первые два элемента и меняет местами, поскольку 5> 1.

(1 5 4 2 8) → (1 4 5 2 8), поменять местами, поскольку 5> 4

(1 4 5 2 8) → (1 4 2 5 8), поменять местами, поскольку 5> 2

(1 4 2 5 8 ) → (1 4 2 5 8 ). Теперь, поскольку эти элементы уже в порядке (8> 5), алгоритм не меняет их местами.

Второй проход

( 1 4 2 5 8) → ( 1 4 2 5 8)

(1 4 2 5 8) → (1 2 4 5 8), поменять местами, поскольку 4> 2

(1 2 4 5 8) → (1 2 4 5 8)

(1 2 4 5 8 ) → (1 2 4 5 8 )

Теперь массив уже отсортирован, но алгоритм не знает, завершился ли он. Алгоритм нужен один весь проход без какой — либо свопа знать сортируется.

Третий проход

( 1 2 4 5 8) → ( 1 2 4 5 8)

(1 2 4 5 8) → (1 2 4 5 8)

(1 2 4 5 8) → (1 2 4 5 8)

(1 2 4 5 8 ) → (1 2 4 5 8 )

Заключение

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

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

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