Здравствуй, дорогой гость. В этой статье я расскажу об алгоритме сортировки массива методом пузырька.
Элементы массива, как пузырьки
Алгоритм пузырьковой сортировки — это довольно простой в реализации алгоритм для сортировки массивов. Можно встретить и другие названия: пузырьковая сортировка, 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. Объявим переменную и инициализируем её значение данными, введенными пользователем.
|
7 8 9 10 |
/* Установим размер массива */ int n; // Кол-во элементов cout << "Количество элементов: "; cin >> n; |
2. Объявим массив из количества элементов, которое ввел пользователь. А то есть объявим массив из n элементов. После запустим цикл и попросим пользователя ввести значение каждого элемента.
|
12 13 14 15 16 17 18 |
/* Заполним массив значениями */ int mass[n]; for(int i = 0; i < n; ++i) { cout << i+1 << "-ый элемент: "; cin >> mass[i]; } |
3. Выведем значения всех элементов массива, используя цикл.
|
20 21 22 23 24 25 26 |
/* Выведем исходный массив */ cout << "Исходный массив: "; for(int i = 0; i < n; ++i) { cout << mass[i] << " "; // Вывод i-го элемента } cout << endl; |
4. Отсортируем массив по убыванию. Здесь нам понадобятся 2 цикла. Первый будет выполнять количество итераций n-1, как в примере выше, который мы разобрали. Второй цикл будет осуществлять проходы по элементам массива (таких проходов n-i) и сравнивать соседние элементы. Элементы сравниваются условием, если i-ый элемент меньше правого соседа, то они меняются местами, таким образом самый маленький элемент будет в правой крайней части.
|
28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
/* Отсортируем массив по убыванию */ for(int i = 1; i < n; ++i) { for(int r = 0; r < n-i; r++) { if(mass[r] < mass[r+1]) { // Обмен местами int temp = mass[r]; mass[r] = mass[r+1]; mass[r+1] = temp; } } } |
5. Выведем отсортированный массив, используя цикл, как в 3-ем действии.
|
43 44 45 46 47 48 49 |
/* Выведем отсортированный массив */ cout << "Отсортированный массив: "; for(int i = 0; i < n; ++i) { cout << mass[i] << " "; } cout << endl; |
Весь код программы
|
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 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
#include <iostream> using namespace std; int main() { /* Установим размер массива */ int n; // Кол-во элементов cout << "Количество элементов: "; cin >> n; /* Заполним массив значениями */ int mass[n]; for(int i = 0; i < n; ++i) { cout << i+1 << "-ый элемент: "; cin >> mass[i]; } /* Выведем исходный массив */ cout << "Исходный массив: "; for(int i = 0; i < n; ++i) { cout << mass[i] << " "; } cout << endl; /* Отсортируем массив по убыванию */ for(int i = 1; i < n; ++i) { for(int r = 0; r < n-i; r++) { if(mass[r] < mass[r+1]) { // Обмен местами int temp = mass[r]; mass[r] = mass[r+1]; mass[r+1] = temp; } } } /* Выведем отсортированный массив */ cout << "Отсортированный массив: "; for(int i = 0; i < n; ++i) { cout << mass[i] << " "; } cout << endl; return 0; } |
Обратите внимание, что в коде программы использовались русские символы, если у вас их отображение некорректно, то почитайте статью про решение проблемы с отображением русских символов в консоли.
Написание программы завершено, теперь проверим результаты. А для этого введем в программу массив, сортировку которого мы произвели, рассматривая пример работы алгоритма немного выше в этой статье.
После ввода данных и выполнения программы мы получили результат.
Результат сортировки массива методом пузырька
Как видно на картинке, массив отсортирован по убыванию. Программа работает.
Как я отмечал ранее, алгоритм работает очень медленно с большим объемом данных, а потому непригоден для использования на практике, а пригоден лишь в обучающих и ознакомительных целях. Посмотрите на решения других задач по программированию.
Везде о ней пишут, но по быстродействию она уступает любым другим. Напишите о QuickSort, будет полезно 🙂
Да, действительно, по быстродействию она уступает многим другим. QuickSort в планах есть, в скором будущем.
А как отсортировать массив по возрастанию?
if(mass[r] < mass[r+1])
поменять здесь знак сравнения на противоположный
ЭЭЭЭ
а разве можно объявлять int mas[n] ???
где n — это int n ??
в C++ статический массив объявляется только константой.
или так: int mas [10] например
или так:
const int n= 5;
int mas[n];
как у Вас это скомпилилось???
Можно, главное чтобы n было присвоено значение.
ПОЛНОСТЬЮ согласен
У меня ваша программа не пошла. Пишет ошибки. Делала через Visual Studio
Работает только если в строку int mass вставить конкретное количество элементов
Согласна с Андреем.
Помогите, проверьте правильность строки int mass[n]
То есть в строке int mass[n] присвоить просто любое значение?
Тогда все идет. А почему, не пойму
Должно быть присвоено значение для переменной n до объявления массива.
Например:
int n =5;
int mass[n];
пишет что нужна константа в int mass[n];
почему бы во втором цикле не присваивать переменной 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;
}
}
}
Ошибка в коде, ибо массив нужен динамический.
int n; // Кол-во элементов
cout <> n;
int *mass = new int[n];
Дальше уже можно писать, как на сайте, только в конце добавить delete [] mass;