Пузырьковая сортировка в C++: главные моменты
Всем привет! Наверно всем прогерам в какой-то момент нужно было отсортировать массив. Сегодня мы разберем алгоритм сортировки с помощью которого вы сможете отсортировать ваш массив или вектор. Вы наверное догадались с названия сегодня пойдет речь о пузырьковой сортировке.
Этот алгоритм очень просто реализовать, но в то же время его главный минус — медленная сортировка.
Что такое пузырьковая сортировка
Пузырьковая сортировка — наверно самая простая сортировка, которую я встречал. Обычно она встречается в книгах по программированию и не выходит за ее пределы. Так как она работает намного медленнее, чем другие алгоритмы сортировки.
Но благодаря ей появились алгоритмы, которые более эффективнее чем она сама. Из таких сортировок можно отметить шейкерную или как еще ее называют сортировка перемешиванием.
Как работает алгоритм пузырьковой сортировки
Принцип работы пузырьковой сортировки можно описать в три пункта:
- Прохождение по всему массиву;
- Сравнивание между собой пар соседних ячеек;
- Если при сравнении оказывается, что значение ячейки
iбольше, чем значение ячейкиi + 1, то мы меняем значения этих ячеек местами;
Ниже вы можете увидеть, как работает пузырьковая сортировка в действии.
Как создать пузырьковую сортировку
Вот что нам придется делать для создания пузырьковой сортировки:
- Создать два цикла
for, чтобы проходить по всем элементам массиваNраз (Nэто размер массива). - Сравнивать ячейки массива, с помощью оператора ветвления
if. - Менять местами значения ячеек.
В примере ниже мы предложили пользователю заполнить массив, который мы дальше отсортируем используя пузырьковую сортировку.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
#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 (здесь находится пузырьковая сортировка):
- В строке 16: мы создали первый цикл
for. - В строке 17: аналогично был создан второй, но уже вложенный цикл.
- В строке 18: происходит сравнивание двух элементов.
- Если результат этого условия положительный, то мы меняем значение элементов.
- Если же результат отрицателен, то мы пропускаем этап смены значений.
- В строке 19: создали переменную
b, чтобы менять значения ячеекdigitals[i]иdigitals[i + 1]местами.
Давайте посмотрим, что выведет программа выше при запуске:
Как улучшить пузырьковую сортировку
Ниже вы можете видеть оптимизированную версию пузырьковой сортировки.
|
1 2 3 4 5 6 7 8 9 10 11 12 |
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).
Дело в том, что за первый полный проход циклом по массиву самый большой элемент всплывет вверх (переместится в конец массива). Второй по размерам элемент всплывет на предпоследнюю ячейку уже за второй проход цикла и т.д.
Поэтому чтобы лишний раз не сравнивать элементы массива тратя на это время, мы решили уменьшать отрезок внутреннего цикла на 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 строчки:
|
1 2 3 |
int b = digitals[j]; digitals[j] = digitals[j + 1]; digitals[j + 1] = b; |
Использовать ее необязательно, потому что она не сделает код быстрее. Но как мы сказали выше, кода станет меньше.
Упражнение
Чтобы закрепить пузырьковую сортировку:
- Заполните массив из 15 элементов случайными числами.
- Отсортируйте массив используя алгоритм пузырьковой сортировки.
- Выведите весь массив на экран.
Мы рады, если в этой статье вы нашли то что и искали. Сегодня мы хотели объяснить принцип работы пузырьковой сортировки. В следующем уроке мы изучим шейкерную сортировку. Если есть вопрос, то пиши в комментарии, мы с радостью вам ответим. Удачи!
Помогите пожалуйста, у меня вместо Русских букв пишется в программе непонятные символы, что делать?
Если вы выводите в консоль, то русские буквы будут превращаться в не читаемые символы. В самой программе это может быть вызвано сменой кодировки.
чтобы писало русские попробуй написать: setlocale (LC_ALL, «Rus»); прямо после начальной скобочки
Наконец разобрался с сортировкой массива пузырьком.
Спасибо автору статьи, который всё написал так, что понятно даже самому идиоту (типа меня).
а нормально что во внутреннем цикле мы идем до 10, при этом проверяя j+1 элемент массива? Мне кажется так работать не будет
Исправил, теперь внутренний цикл до 9. Спасибо!
ничего не понятно! сложна! слишком много букав
никогда комменты не писал, но тут грех не поблагодарить автора за подробное объяснение!
Спасибо, очень доступно
помогите пожалуйста, как вывести весь массив на экран? можно ли как то обозначать другим цветом числа, которые уже отсортированы?
В C++ такой возможности нету, можете поменять себе программу на Visual Studio Code, либо какую нибудь другую которая будет поддерживать.
Этот метод лучше назвать метод «камня», т.к. камень после внутренних перестановок встает на свое место (прикол)
Более изящней указывать место куда должен опуститься камен
for (int i = 9; i >=0; i—) {
bool flag = true;
for (int j = 0; j digitals[j + 1]) {
flag = false;
swap (digitals[j], digitals[j + 1]);
}
}
if (flag) {
break;
}
}