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

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

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

Интересное

Последние новости в мире программирования

Самые свежие новости и полезные материалы в моем telegram канале.

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

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

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

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

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

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

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

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

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

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

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

#include <iostream>

using namespace std;

int main() {
  setlocale(LC_ALL, "rus");

  int digitals[10]; // объявили массив на 10 ячеек

  cout << "Введите 10 чисел для заполнения массива: " << endl;

  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 << digitals[i] << " "; // выводим элементы массива
  }
  system("pause");
  return 0;
}

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

1. В строке 16: мы создали первый цикл for.
2. В строке 17: аналогично был создан второй, но уже вложенный цикл.
3. В строке 18: происходит сравнивание двух элементов.
   • Если результат этого условия положительный, то мы меняем значение элементов.
   • Если же результат отрицателен, то мы пропускаем этап смены значений.
4. В строке 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.

Интересное

Последние новости в мире программирования

Самые свежие новости и полезные материалы в моем telegram канале.

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

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

  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;
    }
  }

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

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 строчки:

int b = digitals[j]; 
digitals[j] = digitals[j + 1]; 
digitals[j + 1] = b;

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

Упражнение

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

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

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

« Шейкер сортировка в C++

Бинарный поиск в C++ »