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

Пузырьковая сортировка в языке программирования C++Пузырьковая сортировка — самый простой из методов сортировки.

В методе пузырьковой сортировки каждый элемент списка сравнивается с соседним элементом. Таким образом, если в списке A n элементов, то A[0] сравнивается с A[1], A[1] сравнивается с A[2] и так далее.

После сравнения, если первый элемент больше второго, два элемента меняются местами.

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

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

Шаг 1 : Для i = 0 до N-1 запускаем шаг 2
Шаг 2 : Для J = i + 1 до N – повторяем
Шаг 3 : Если A[J] > A[i]
Меняем местами A[J] и A[i ]
[Конец внутреннего цикла for]
[Конец внешнего цикла for]
Шаг 4 : Выход

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

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

Читать также:  Двусвязный список структуры данных в C++

Псевдокод:

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

алгоритм пузырьковой сортировки

Алгоритм пузырьковой сортировки проход 2

Алгоритм пузырьковой сортировки проход 3

Массив полностью отсортирован.

Приведенные выше схемы можно обобщить в табличной форме, как показано ниже:

Проход Несортированый список Сравнение Отсортированный список
1 {10,5,15,0,12} {10,5} {5,10,15,0,12}
{5,10,15,0,12} {10,15} {5,10,15,0,12}
{5,10,15,0,12} {15,0} {5,10,0,15,12}
{5,10,0,15,12} {15,12} {5,10,0,12,15}
2 {5,10,0,12,15} {5,10} {5,10,0,12,15}
{5,10,0,12,15} {10,0} {5,0,10,12,15}
{5,0,10,12,15} {10,12} {5,0,10,12,15}
3 {5,0,10,12,15} {5,0} {0,5,10,12,15}
{5,0,10,12,15} {5,10} {5,0,10,12,15}
{5,0,10,12,15} СОРТИРОВКА

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

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

Когда мы достигнем N-1 (где N — общее количество элементов в списке) проходов, весь список будет отсортирован.

Метод пузырьковой сортировки может быть реализован на любом языке программирования. Ниже мы реализовали алгоритм пузырьковой сортировки с использованием языков C++ и Java.

Читать также:  Строки в C++ с примерами

Давайте посмотрим пример пузырьковой сортировки на языке C++:

Вывод данных:

Список ввода…
10 2 0 14 43 25 18 1 5 45
Отсортированный список элементов…
0 1 2 5 10 14 18 25 43 45
Количество проходов для сортировки списка: 10

Теперь, давайте посмотрим пример пузырьковой сортировки на языке Java:

Вывод данных:

Список входных данных…
10 -2 0 14 43 25 18 1 5 45
Отсортированный список
-2 0 1 5 10 14 18 25 43 45
Количество проходов, необходимых для завершения сортировки:10

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

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

Анализ сложности алгоритма пузырьковой сортировки

Из псевдокода и схем, которые мы представили выше, в пузырьковой сортировке мы делаем N-1 сравнений на первом проходе, N-2 сравнений на втором проходе и так далее.

Следовательно, общее количество сравнений в пузырьковой сортировке равно:

Сумма = (N-1) + (N-2) + (N-3)+ … + 3 + 2 + 1

= N(N-1)/2

= O(n2) => временная сложность метода пузырьковой сортировки

Читать также:  Полиморфизм времени выполнения в C++

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

Временная сложность в худшем случае O(n 2)
Временная сложность в лучшем случае O(n)
Средняя временная сложность O(n 2)
Пространственная сложность O(1)

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

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

Итог

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

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

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

В нашей следующей статье мы подробно поговорим о сортировке выбором в C++.

С Уважением, МониторБанк

Добавить комментарий