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

Пузырьковая сортировка в C++: главные моменты

Всем привет! Наверно всем прогерам в какой-то момент нужно было отсортировать массив. Сегодня мы разберем алгоритм сортировки с помощью которого вы сможете отсортировать ваш массив или вектор. Вы наверное догадались с названия сегодня пойдет речь о пузырьковой сортировке.

Этот алгоритм очень просто реализовать, но в то же время его главный минус — медленная сортировка.

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

Пузырьковая сортировка — наверно самая простая сортировка, которую я встречал. Обычно она встречается в книгах по программированию и не выходит за ее пределы. Так как она работает намного медленнее, чем другие алгоритмы сортировки.

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

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

Принцип работы пузырьковой сортировки можно описать в три пункта:

  1. Прохождение по всему массиву;
  2. Сравнивание между собой пар соседних ячеек;
  3. Если при сравнении оказывается, что значение ячейки i больше, чем значение ячейки i + 1, то мы меняем значения этих ячеек местами;

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

 

Как работает пузырьковая сортировка на гифке

Как это сделать Как создать пузырьковую сортировку

Вот что нам придется делать для создания пузырьковой сортировки:

  • Создать два цикла for, чтобы проходить по всем элементам массива N раз (N это размер массива).
  • Сравнивать ячейки массива, с помощью оператора ветвления if.
  • Менять местами значения ячеек.

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

Давайте поподробнее разберем строки 16 — 24 (здесь находится пузырьковая сортировка):

  1. В строке 16: мы создали первый цикл for.
  2. В строке 17: аналогично был создан второй, но уже вложенный цикл.
  3. В строке 18: происходит сравнивание двух элементов.
    • Если  результат этого условия положительный, то мы меняем значение элементов.
    • Если же результат отрицателен, то мы пропускаем этап смены значений.
  4. В строке 19: создали переменную b, чтобы менять значения ячеек digitals[i] и digitals[i + 1] местами.

Давайте посмотрим, что выведет программа выше при запуске:

sort_puzerek.cpp
Введите 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.

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

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

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

  1. В строке 17: изменили условие внутреннего цикла на i < 10 - ( i + 1).

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

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

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

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

Вы также можете объявить переменную flag типа int и вместо true или false хранить в переменной значение 1 и 0.

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

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

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

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

Завершение урока домашним заданием Упражнение

Чтобы закрепить пузырьковую сортировку:

  1. Заполните массив из 15 элементов случайными числами.
  2. Отсортируйте массив используя алгоритм пузырьковой сортировки.
  3. Выведите весь массив на экран.

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




Комментарии к записи “Пузырьковая сортировка в C++: главные моменты”
  • Даниил:

    Помогите пожалуйста, у меня вместо Русских букв пишется в программе непонятные символы, что делать?

    • Дмитрий:

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

    • Станислав:

      чтобы писало русские попробуй написать: setlocale (LC_ALL, «Rus»); прямо после начальной скобочки

  • Семен:

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

  • Глеб:

    а нормально что во внутреннем цикле мы идем до 10, при этом проверяя j+1 элемент массива? Мне кажется так работать не будет

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

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