Сортировка пузырьком.
Описание алгоритма и его реализация на Python
Сортировка пузырьком — это метод сортировки массивов и списков путем последовательного сравнения соседних элементов и их обмена, если предшествующий оказывается больше последующего (при сортировке по возрастанию).
В процессе выполнения данного алгоритма элементы с большими значениями оказываются в конце списка, а элементы с меньшими значениями постепенно перемещаются по направлению к началу списка. Образно говоря, тяжелые элементы падают на дно, а легкие медленно всплывают подобно пузырькам воздуха. При этом в начале сортировки отсортированным становится конец списка, а не его начало.
В сортировке методом пузырька количество итераций внешнего цикла определяется длинной списка минус единица, так как когда второй элемент становится на свое место, то первый уже однозначно минимальный и не требует сортировки.
Количество итераций внутреннего цикла зависит от номера итерации внешнего цикла, так как конец списка уже отсортирован, и выполнять проход по этим элементам смысла нет.
Пусть имеется список из пяти элементов [6, 12, 4, 3, 8].
За первую итерацию внешнего цикла число 12 переместится в конец. Для этого потребуется 4 сравнения во внутреннем цикле:
- 6 > 12? Нет
- 12 > 4? Да. Меняем местами
- 12 > 3? Да. Меняем местами
- 12 > 8? Да. Меняем местами
Результат: [6, 4, 3, 8, 12]
За вторую итерацию внешнего цикла число 8 переместиться на предпоследнее место. Для этого потребуется 3 сравнения:
- 6 > 4? Да. Меняем местами
- 6 > 3? Да. Меняем местами
- 6 > 8? Нет
Результат: [4, 3, 6, 8, 12]
На третьей итерации внешнего цикла исключаются два последних элемента. Количество итераций внутреннего цикла равно двум:
- 4 > 3? Да. Меняем местами
- 4 > 6? Нет
Результат: [3, 4, 6, 8, 12]
На четвертой итерации внешнего цикла осталось сравнить только первые два элемента, поэтому количество итераций внутреннего равно единице:
Результат: [3, 4, 6, 8, 12]
Реализация сортировки пузырьком на языке программирования Python с помощью циклов for
from random import randint N = 10 # количество элементов в списке a = [] for i in range(N): a.append(randint(1, 99)) print(a) # вывод исходного неотсортированного списка # Сама сортировка методом "пузырька" for i in range(N-1): for j in range(N-1-i): if a[j] > a[j+1]: a[j], a[j+1] = a[j+1], a[j] print(a) # вывод отсортированного списка
Пример выполнения кода:
[63, 80, 62, 69, 71, 37, 12, 90, 19, 67] [12, 19, 37, 62, 63, 67, 69, 71, 80, 90]
Для сортировки по убыванию достаточно изменить знак операции сравнения при if на обратный.
Примечание. Выражение a[j], a[j+1] = a[j+1], a[j] — это позволительная в Python сокращенная запись обмена значений двух переменных (в данном случае «ячеек» списка). Рабочий вариант для большинства языков программирования будет выглядеть так:
buff = a[j] a[j] = a[j+1] a[j+1] = buff
С помощью циклов while :
from random import randint N = 10 # Вариант заполнения списка с помощью спискового выражения: a = [randint(1, 99) for n in range(N)] print(a) i = 0 while i N-1: j = 0 while j N-1-i: if a[j] > a[j+1]: a[j], a[j+1] = a[j+1], a[j] j += 1 i += 1 print(a)
Функция сортировки пузырьком на Python:
from random import randint def bubble(array): iterations = len(array) - 1 for i in range(iterations): for j in range(iterations-i): if array[j] > array[j+1]: array[j], array[j+1] = array[j+1], array[j] a = [randint(1, 99) for n in range(10)] print(a) bubble(a) print(a)
X Скрыть Наверх
Решение задач на Python
Сортировка пузырьком
Сортировка простыми обменами, сортировка пузырьком (англ. bubble sort) — один из квадратичных алгоритмов сортировки.
Алгоритм
Алгоритм состоит в повторяющихся проходах по сортируемому массиву. На каждой итерации последовательно сравниваются соседние элементы, и, если порядок в паре неверный, то элементы меняют местами. За каждый проход по массиву как минимум один элемент встает на свое место, поэтому необходимо совершить не более [math] n — 1 [/math] проходов, где [math] n [/math] размер массива, чтобы отсортировать массив.
Ниже приведен псевдокод сортировки пузырьком, на вход которой подается массив [math] a[0..n — 1] [/math] .
function bubbleSort(a): for i = 0 to n - 2 for j = 0 to n - 2 if a[j] > a[j + 1] swap(a[j], a[j + 1])
Оптимизация
- Можно заметить, что после [math] i [/math] -ой итерации внешнего цикла [math] i [/math] последних элементов уже находятся на своих местах в отсортированном порядке, поэтому нет необходимости производить их сравнения друг с другом. Следовательно, внутренний цикл можно выполнять не до [math] n — 2 [/math] , а до [math] n — i — 2 [/math] .
- Также заметим, что если после выполнения внутреннего цикла не произошло ни одного обмена, то массив уже отсортирован, и продолжать что-то делать бессмысленно. Поэтому внутренний цикл можно выполнять не [math] n — 1 [/math] раз, а до тех пор, пока во внутреннем цикле происходят обмены.
При использовании первой оптимизации сортировка принимает следующий вид:
function bubbleSort(a): for i = 0 to n - 2 for j = 0 to n - i - 2 if a[j] > a[j + 1] swap(a[j], a[j + 1])
При использовании же обеих оптимизаций сортировка пузырьком выглядит так:
function bubbleSort(a): i = 0 t = true while t t = false for j = 0 to n - i - 2 if a[j] > a[j + 1] swap(a[j], a[j + 1]) t = true i = i + 1
Сложность
В данной сортировке выполняются всего два различных вида операции: сравнение элементов и их обмен. Поэтому время всего алгоритма [math] T = T_1 + T_2 [/math] , где [math] T_1 [/math] — время, затрачиваемое на сравнение элементов, а [math] T_2 [/math] — время, за которое мы производим все необходимые обмены элементов.
Так как в алгоритме меняться местами могут только соседние элементы, то каждый обмен уменьшает количество инверсий на единицу. Следовательно, количество обменов равно количеству инверсий в исходном массиве вне зависимости от реализации сортировки. Максимальное количество инверсий содержится в массиве, элементы которого отсортированы по убыванию. Несложно посчитать, что количество инверсий в таком массиве [math] \frac [/math] . Получаем, что [math] T_2 = O(n^2) [/math] .
В неоптимизированной реализации на каждой итерации внутреннего цикла производятся [math] n — 1 [/math] сравнений, а так как внутренний цикл запускается также [math] n — 1 [/math] раз, то за весь алгоритм сортировки производятся [math] (n — 1)^2 [/math] сравнений.
В оптимизированной версии точное количество сравнений зависит от исходного массива. Известно, что худший случай равен [math] \frac [/math] , а лучший — [math] n-1 [/math] . Следовательно, [math] T_1 = O(n^2) [/math] .
В итоге получаем [math] T = T_1 + T_2 = O(n^2) + O(n^2) = O(n^2) [/math] .
Пример работы алгоритма
Возьмём массив [math] [5, 1, 4, 2, 8] [/math] и отсортируем значения по возрастанию, используя сортировку пузырьком. Выделены те элементы, которые сравниваются на данном этапе.
Первый проход:
| До | После | Описание шага |
|---|---|---|
| 5 1 4 2 8 | 1 5 4 2 8 | Здесь алгоритм сравнивает два первых элемента и меняет их местами. |
| 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 |
Теперь массив полностью отсортирован, но неоптимизированный алгоритм проведет еще два прохода, на которых ничего не изменится, в отличие от алгоритма, использующего вторую оптимизацию, который сделает один проход и прекратит свою работу, так как не сделает за этот проход ни одного обмена.
Модификации
Сортировка чет-нечет
Сортировка чет-нечет (англ. odd-even sort) — модификация пузырьковой сортировки, основанная на сравнении элементов стоящих на четных и нечетных позициях независимо друг от друга. Сложность — [math] O(n^2) [/math] . Псевдокод указан ниже:
function oddEvenSort(a): for i = 0 to n - 1 if i mod 2 == 0 for j = 2 to n - 1 step 2 if a[j] < a[j - 1] swap(a[j - 1], a[j]) else for j = 1 to n - 1 step 2 if a[j] < a[j - 1] swap(a[j - 1], a[j])
Преимущество этой сортировки — на нескольких процессорах она выполняется быстрее, так как четные и нечетные индексы сортируются параллельно.
Сортировка расческой
Сортировка расческой (англ. comb sort) — модификация пузырьковой сортировки, основанной на сравнении элементов на расстоянии. Сложность — [math] O(n^2) [/math] , но стремится к [math] O(n \log n) [/math] . Является самой быстрой квадратичной сортировкой. Недостаток — она неустойчива. Псевдокод указан ниже:
function combSort(a): k = 1.3 jump = n bool swapped = true while jump > 1 and swapped if jump > 1 jump /= k swapped = false for i = 0 to size - jump - 1 if a[i + jump] < a[i] swap(a[i], a[i + jump]) swapped = true
Пояснения: Изначально расстояние между сравниваемыми элементами равно [math] \frac [/math] , где [math] k = 1<.>3 [/math] — оптимальное число для этого алгоритма. Сортируем массив по этому расстоянию, потом уменьшаем его по этому же правилу. Когда расстояние между сравниваемыми элементами достигает единицы, массив досортировывается обычным пузырьком.
Сортировка перемешиванием
Сортировка перемешиванием (англ. cocktail sort), также известная как Шейкерная сортировка — разновидность пузырьковой сортировки, сортирующая массив в двух направлениях на каждой итерации. В среднем, сортировка перемешиванием работает в два раза быстрее пузырька. Сложность — [math] O(n^2) [/math] , но стремится она к [math] O(k \cdot n) [/math] , где [math] k [/math] — максимальное расстояние элемента в неотсортированном массиве от его позиции в отсортированном массиве. Псевдокод указан ниже:
function shakerSort(a): begin = -1 end = n - 2 while swapped swapped = false begin++ for i = begin to end if a[i] > a[i + 1] swap(a[i], a[i + 1]) swapped = true if !swapped break swapped = false end-- for i = end downto begin if a[i] > a[i + 1] swap(a[i], a[i + 1]) swapped = true
См. также
- Сортировка выбором
- Сортировка вставками
- Сортировка кучей
- Сортировка слиянием
- Быстрая сортировка
- Сортировка подсчетом
Источники информации
- Сортировка пузырьком — Википедия
- Визуализатор
- Сортировка чет-нечет — Википедия
- Сортировка расческой — Википедия
- Сортировка перемешиванием — Википедия
Пузырьковая сортировка в C++: главные моменты
Всем привет! Наверно всем прогерам в какой-то момент нужно было отсортировать массив. Сегодня мы разберем алгоритм сортировки с помощью которого вы сможете отсортировать ваш массив или вектор. Вы наверное догадались с названия сегодня пойдет речь о пузырьковой сортировке.
Этот алгоритм очень просто реализовать, но в то же время его главный минус - медленная сортировка.
Что такое пузырьковая сортировка
Пузырьковая сортировка - наверно самая простая сортировка, которую я встречал. Обычно она встречается в книгах по программированию и не выходит за ее пределы. Так как она работает намного медленнее, чем другие алгоритмы сортировки.
Но благодаря ей появились алгоритмы, которые более эффективнее чем она сама. Из таких сортировок можно отметить шейкерную или как еще ее называют сортировка перемешиванием.
Как работает алгоритм пузырьковой сортировки
Принцип работы пузырьковой сортировки можно описать в три пункта:
- Прохождение по всему массиву;
- Сравнивание между собой пар соседних ячеек;
- Если при сравнении оказывается, что значение ячейки i больше, чем значение ячейки i + 1 , то мы меняем значения этих ячеек местами;
Ниже вы можете увидеть, как работает пузырьковая сортировка в действии.
Как создать пузырьковую сортировку
Вот что нам придется делать для создания пузырьковой сортировки:
- Создать два цикла for , чтобы проходить по всем элементам массива N раз ( N это размер массива).
- Сравнивать ячейки массива, с помощью оператора ветвления if .
- Менять местами значения ячеек.
В примере ниже мы предложили пользователю заполнить массив, который мы дальше отсортируем используя пузырьковую сортировку.
#include using namespace std; int main() setlocale(LC_ALL, "rus"); int digitals[10]; // объявили массив на 10 ячеек cout <"Введите 10 чисел для заполнения массива: " ; for (int i = 0; i 10; i++) cin >> digitals[i]; // "читаем" элементы в массив > for (int i = 0; i 10; i++) for (int j = 0; j 9; j++) if (digitals[j] > digitals[j + 1]) int b = digitals[j]; // создали дополнительную переменную digitals[j] = digitals[j + 1]; // меняем местами digitals[j + 1] = b; // значения элементов > > > cout <"Массив в отсортированном виде: "; for (int i = 0; i 10; i++) cout [ i] <" "; // выводим элементы массива > system("pause"); return 0; > Давайте поподробнее разберем строки 16 - 24 (здесь находится пузырьковая сортировка):
- В строке 16: мы создали первый цикл for .
- В строке 17: аналогично был создан второй, но уже вложенный цикл.
- В строке 18: происходит сравнивание двух элементов.
- Если результат этого условия положительный, то мы меняем значение элементов.
- Если же результат отрицателен, то мы пропускаем этап смены значений.
- В строке 19: создали переменную b , чтобы менять значения ячеек digitals[i] и digitals[i + 1] местами.
Давайте посмотрим, что выведет программа выше при запуске:
Введите 10 чисел для заполнения массива: 5 3 6 2 7 0 2 8 9 10 Массив в отсортированном виде: 0 2 2 3 5 6 7 8 9 10 Process returned 0 (0x0) execution time : 0.005 s Press any key to continue.Как улучшить пузырьковую сортировку
Ниже вы можете видеть оптимизированную версию пузырьковой сортировки.
for (int i = 0; i 10; i++) bool flag = true; for (int j = 0; j 10 - (i + 1); j++) if (digitals[j] > digitals[j + 1]) flag = false; swap (digitals[j], digitals[j + 1]); > > if (flag) break; > >
Давайте посмотрим, что мы сделали для ее оптимизации:
-
В строке 17: изменили условие внутреннего цикла на i < 10 - ( i + 1) .
Дело в том, что за первый полный проход циклом по массиву самый большой элемент всплывет вверх (переместится в конец массива). Второй по размерам элемент всплывет на предпоследнюю ячейку уже за второй проход цикла и т.д.
Для этого в строке 5: чтобы пузырьковая сортировка останавливалась (когда массив уже стал отсортирован), мы объявили булеву переменную flag (ее обычно называют флаг или флажок). Еще при ее инициализации мы поместили значение true , но она меняется на:
- false , если результат условия в строке 4: положительный.
Вы также можете объявить переменную flag типа int и вместо true или false хранить в переменной значение 1 и 0.
А в строке 9: чтобы мы могли выйти из алгоритма мы проверяем:
- Если булева переменная равна true , значит массив уже полностью отсортирован и можно выйти. Для этого используем оператор break .
- Если же значение flag равно false , то продолжаем сортировать массив.
В строке 6: вы (возможно) увидели незнакомую функцию swap . Если коротко описать что она делает, то она принимает два аргумента (через запятую) и меняет их значения местами. В нашем случаи она принимает ячейки digitals[j] и digitals[j + 1] . Мы использовали эту функцию чтобы не писать вот эти 3 строчки:
int b = digitals[j]; digitals[j] = digitals[j + 1]; digitals[j + 1] = b;Использовать ее необязательно, потому что она не сделает код быстрее. Но как мы сказали выше, кода станет меньше.
Чтобы закрепить пузырьковую сортировку:
- Заполните массив из 15 элементов случайными числами.
- Отсортируйте массив используя алгоритм пузырьковой сортировки.
- Выведите весь массив на экран.
Мы рады, если в этой статье вы нашли то что и искали. Сегодня мы хотели объяснить принцип работы пузырьковой сортировки. В следующем уроке мы изучим шейкерную сортировку. Если есть вопрос, то пиши в комментарии, мы с радостью вам ответим. Удачи!
Читайте также
Функция sort и компаратор в C++
Что такое сортировка, как ею управлять - все ответы находятся в этой статье. Вот что вы узнаете после прочтения данной статьи: что такое компаратор, как использовать стандартную сортировку, как сортировка работает для вектора или списка.
Массивы в C++
В данном уроке мы научимся работать с массивами. Массивы являются самым популярным способом хранения больших объемов данных. Поэтому давайте разбираться!
Цикл do while в C++
В очередном уроке по C++ мы пройдем цикл do while. В этом уроке вы узнаете как его просто реализовать и закрепим пройденные знания на примере. Удачи!
Динамические массивы и переменные в C++
Как пользоваться динамическими переменными и массивами в C++. Мы разберем как их создать и узнаем их плюсы перед использованием обычных массивов.
Функция copy в C++
В этом уроке вы узнаете что такое функция copy, как ее использовать. А также узнаете с какими контейнерами она работает.
Векторы в C++
В этом уроке вы узнаете, что такое вектор в C++, а также если вы хотите узнать, как правильно пользоваться и какие функции к им применять - то вам сюда.
Цикл for в C++
В данной статье мы разберем работы цикла for на примерах. Также мы поговорим о распространенных ошибках, которые возникают при работе с циклами.
vector::push_back в C++
Язык C++ предоставляет различные способы работы с данными. Функция push_back - это популярный метод добавления элементов в вектор. В этой статье мы подробно рассмотрим эту функцию, разберемся, как и когда её использовать, и обсудим некоторые интересные моменты, связанные с ней.
Стек (stack) в C++
В этой статье вы познакомитесь с структурой данных стек. Мы разберем что это за зверь и как им пользоваться в своей программе. Также мы изучим стек через массив.
Мы рассмотрим создание программы, ее структуру, а также главные правила синтаксиса языка C++.
Список list в C++
В этой статье мы разберемся со списками в C++. Мы узнаем что такое list, как его создать, как им пользоваться и подведем итоги.
Указатели в C++
В этом уроке мы разберем, как создать и исполь