В этом материале мы поговорим про алгоритм сортировки пузырьком (Bubble sort). Для примера попробуем отсортировать массив вручную, после чего напишем код для сортировки пузырьком на языке программирования Python и Си шарп.

Описание алгоритма

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

Проговорим алгоритм еще раз:

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

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

Рассмотрим пример

Представьте, что у нас есть следующий массив: 

7 2 9 4 1 0

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

7 9 4 1 0

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

2 7 4 1 0 9

Первая итерация закончена, количество шагов уменьшилось на 1 (n-1), то есть 9 находится там, где надо. Больше это число не затрагивается.

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

2 4 1 0 7 9

И так далее. Итоговый вид массива после сортировки по методу пузырьком вы можете видеть ниже:

0 1 2 4 7 9

Как видите, ничего сложного в этом нет.

Реализация на Си шарп

Чтобы реализовать сортировку пузырьком, сначала над создать саму функцию сортировки, которая будет располагаться в итоге перед функцией main:

 static int[] BubbleSort(int[] mas)

        {

            int temp;

            for (int i = 0; i < mas.Length; i++)

            {

                for (int j = i + 1; j < mas.Length; j++)

                {

                    if (mas[i] > mas[j])

                    {

                        temp = mas[i];

                        mas[i] = mas[j];

                        mas[j] = temp;

                    }                  

                }           

            }

            return mas;

        }

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

Пузырьковая сортировка на Python и С#

Реализация на Python

Теперь давайте попробуем выполнить сортировку пузырьком c «Пайтон»:

Пузырьковая сортировка на Python и С#
Пузырьковая сортировка на Python и С#

По материалам:

  • https://all-python.ru/primery/puzyryok.html;
  • https://csharp.webdelphi.ru/sortirovka-massiva-c-algoritm-sortirovka-puzyrkom/;
  • https://vscode.ru/prog-lessons/sortirovka-metodom-puzyirka-c-sharp.html.