Зачем два цикла в пузырьковом методе
Перейти к содержимому

Зачем два цикла в пузырьковом методе

  • автор:

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

обложка статьи

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

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

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

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

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

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

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

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

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

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

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

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

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

#include using namespace std; int main()  setlocale(LC_ALL, "rus"); int digitals[10]; // объявили массив на 10 ячеек cout  <"Введите 10 чисел для заполнения массива: "  ; 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  [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.

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

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

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

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

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

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

Для этого в строке 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. Выведите весь массив на экран.

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

Читайте также

Функция sort и компаратор в C++

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

Массивы в C++

В данном уроке мы научимся работать с массивами. Массивы являются самым популярным способом хранения больших объемов данных. Поэтому давайте разбираться!

Цикл do while в C++

В очередном уроке по C++ мы пройдем цикл do while. В этом уроке вы узнаете как его просто реализовать и закрепим пройденные знания на примере. Удачи!

Динамические массивы и переменные в C++

Как пользоваться динамическими переменными и массивами в C++. Мы разберем как их создать и узнаем их плюсы перед использованием обычных массивов.

Функция copy в C++

В этом уроке вы узнаете что такое функция copy, как ее использовать. А также узнаете с какими контейнерами она работает.

Векторы в C++

В этом уроке вы узнаете, что такое вектор в C++, а также если вы хотите узнать, как правильно пользоваться и какие функции к им применять — то вам сюда.

Цикл for в C++

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

vector::push_back в C++

Язык C++ предоставляет различные способы работы с данными. Функция push_back — это популярный метод добавления элементов в вектор. В этой статье мы подробно рассмотрим эту функцию, разберемся, как и когда её использовать, и обсудим некоторые интересные моменты, связанные с ней.

Стек (stack) в C++

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

Мы рассмотрим создание программы, ее структуру, а также главные правила синтаксиса языка C++.
Список list в C++

В этой статье мы разберемся со списками в C++. Мы узнаем что такое list, как его создать, как им пользоваться и подведем итоги.

Указатели в C++

В этом уроке мы разберем, как создать и исполь

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

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