Алгоритм пузырьковой сортировки одномерного массива на C++

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

Элементы массива, как пузырьки

Элементы массива, как пузырьки

Алгоритм пузырьковой сортировки — это довольно простой в реализации алгоритм для сортировки массивов. Можно встретить и другие названия: пузырьковая сортировка, Buble sort или сортировка простыми обменами — но все они будут обозночать один и тот же алгоритм. Назван так, потому что большее или меньшее значение «всплывает» (сдвигается) к краю массива после каждой итерации, это будет видно в примере.

Сложность этого алгоритма выражается формулой О(n^2) (n в степени 2). Алгоритм работает медленно с большими массивами, а поэтому малоэффективен и на практике используется редко, чаще всего в учебных целях. Для сортировки массивов на практике используют другие более быстрые алгоритмы, один из них —  QuickSort(быстрая сортировка). Функция для быстрой сортировки включена во многие стандартные библиотеки языков программирования, например в языке C функция qsort() из стандартной библиотеки.

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

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

Рассмотрим пример работы алгоритма с массивом, состоящим из четырех элементов.

Имеется массив [4, 5, 2, 6]. Сортировать его будем по убыванию.

N — количество элементов в массиве. i — номер прохода. Алгоритм будет делать проходы по массиву, всего N-1 проходов до N-i ячейки в каждой итерации для любого массива.

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

4 5 2 6

Сравниваем 4 и 5, 4 меньше 5, а значит мы их меняем местами.

Следующий проход.

5 4 2 6

Сравниваем 4 и 2, 4 не меньше 2, а значит пропускаем и идем дальше.

5 4 2 6

Сравниваем 2 и 6, 4 меньше 6, а значит мы их меняем местами.

Теперь мы у нас массив [5, 4 ,6, 2]. Как видно, он еще не упорядочен до конца. После первого прохода в конец массива передвинулось самое маленькое значение, теперь нам нужно сделать еще проход до элемента N-2 (ведь идет 2-ая итерация).

Делаем проход, начиная с первого элемента.

5 4 6 2

Сравниваем 5 и 4, 5 не меньше 4, а значит пропускаем и идем дальше.

5 4 6 2

Сравниваем 6 и 4, 6 меньше 4, а значит мы их меняем местами. Мы достигли элемента N-2, завершаем итерацию.

Теперь мы имеем массив [5, 6, 4, 2]. 2 последних элемента упорядочены как нужно. Для завершения нужно выполнить еще один проход до N-3.

5 6 4 2

Сравниваем 5 и 6, 5 меньше 6, а значит мы их меняем местами. Мы достигли элемента N-3, завершаем итерацию.

В итоге на выходе мы получили массив упорядоченный по убыванию — [6, 5, 4, 2].

Реализация алгоритма на языке C++

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

  1. Установит размер массива, прося пользователя ввести числовое значение.
  2. Заполнит массив значениями, введенными пользователем для каждого элемента массива.
  3. Выведет исходный массив.
  4. Отсортирует массив по убыванию.
  5. Выведет отсортированный массив.

Теперь собственно код по каждому из пунктов.

1. Объявим переменную и инициализируем её значение данными, введенными пользователем.

2. Объявим массив из количества элементов, которое ввел пользователь. А то есть объявим массив из n элементов. После запустим цикл и попросим пользователя ввести значение каждого элемента.

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

4. Отсортируем массив по убыванию. Здесь нам понадобятся 2 цикла. Первый будет выполнять количество итераций n-1, как в примере выше, который мы разобрали. Второй цикл будет осуществлять проходы по элементам массива (таких проходов n-i) и сравнивать соседние элементы. Элементы сравниваются условием, если i-ый элемент меньше правого соседа, то они меняются местами, таким образом самый маленький элемент будет в правой крайней части.

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

Весь код программы

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

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

После ввода данных и выполнения программы мы получили результат.

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

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

Как видно на картинке, массив отсортирован по убыванию. Программа работает.

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

Алгоритм пузырьковой сортировки одномерного массива на C++: 13 комментариев

  1. Tima

    Везде о ней пишут, но по быстродействию она уступает любым другим. Напишите о QuickSort, будет полезно 🙂

    1. Nicknixer Автор записи

      Да, действительно, по быстродействию она уступает многим другим. QuickSort в планах есть, в скором будущем.

  2. Безымянный

    А как отсортировать массив по возрастанию?

    1. Марсель

      if(mass[r] < mass[r+1])
      поменять здесь знак сравнения на противоположный

  3. Andrey

    ЭЭЭЭ
    а разве можно объявлять int mas[n] ???
    где n — это int n ??
    в C++ статический массив объявляется только константой.

    или так: int mas [10] например
    или так:
    const int n= 5;
    int mas[n];

    как у Вас это скомпилилось???

  4. Larisa

    У меня ваша программа не пошла. Пишет ошибки. Делала через Visual Studio

  5. Larisa

    Работает только если в строку int mass вставить конкретное количество элементов

  6. Larisa

    Согласна с Андреем.
    Помогите, проверьте правильность строки int mass[n]

  7. Larisa

    То есть в строке int mass[n] присвоить просто любое значение?
    Тогда все идет. А почему, не пойму

  8. usa_rulit

    почему бы во втором цикле не присваивать переменной i2 переменную цикла i, ведь это с каждой итерацией уменьшает количество итераций второго цикла?
    for (int i = 0; i < 6; i++) {
    for (int i2 = i; i2 m1[i2 + 1])
    {
    a = m1[i2]; m1[i2] = m1[i2 + 1]; m1[i2 + 1]=a;
    }
    }

    }

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

Ваш e-mail не будет опубликован. Обязательные поля помечены *