Алгоритм пузырьковой сортировки одномерного массива на C++

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

Элементы массива, как пузырьки

Алгоритм пузырьковой сортировки — это довольно простой в реализации алгоритм для сортировки массивов. Можно встретить и другие названия: пузырьковая сортировка, 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. Объявим переменную и инициализируем её значение данными, введенными пользователем.

/* Установим размер массива */
int n; // Кол-во элементов
cout << "Количество элементов: ";
cin >> n;

/* Установим размер массива */

int n; // Кол-во элементов

cout << "Количество элементов: ";

cin >> n;

2. Объявим массив из количества элементов, которое ввел пользователь. А то есть объявим массив из n элементов. После запустим цикл и попросим пользователя ввести значение каждого элемента.

/* Заполним массив значениями */
int mass[n];
for(int i = 0; i < n; ++i)
{
	cout << i+1 << "-ый элемент: ";
	cin >> mass[i]; 
}

/* Заполним массив значениями */

int mass[n];

for(int i = 0; i < n; ++i)

{

cout << i+1 << "-ый элемент: ";

cin >> mass[i];

}

3. Выведем значения всех элементов массива, используя цикл.

/* Выведем исходный массив */
cout << "Исходный массив: ";
for(int i = 0; i < n; ++i)
{
	cout << mass[i] << " "; // Вывод i-го элемента
}
cout << endl;

/* Выведем исходный массив */

cout << "Исходный массив: ";

for(int i = 0; i < n; ++i)

{

cout << mass[i] << " "; // Вывод i-го элемента

}

cout << endl;

4. Отсортируем массив по убыванию. Здесь нам понадобятся 2 цикла. Первый будет выполнять количество итераций n-1, как в примере выше, который мы разобрали. Второй цикл будет осуществлять проходы по элементам массива (таких проходов n-i) и сравнивать соседние элементы. Элементы сравниваются условием, если i-ый элемент меньше правого соседа, то они меняются местами, таким образом самый маленький элемент будет в правой крайней части.

/* Отсортируем массив по убыванию */
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;
		}
	}
}

/* Отсортируем массив по убыванию */

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-ем действии.

/* Выведем отсортированный массив */
cout << "Отсортированный массив: ";
for(int i = 0; i < n; ++i)
{
	cout << mass[i] << " ";
}
cout << endl;

/* Выведем отсортированный массив */

cout << "Отсортированный массив: ";

for(int i = 0; i < n; ++i)

{

cout << mass[i] << " ";

}

cout << endl;

Весь код программы

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

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

}

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

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

После ввода данных и выполнения программы мы получили результат.

Результат сортировки массива методом пузырька

Как видно на картинке, массив отсортирован по убыванию. Программа работает.

Как я отмечал ранее, алгоритм работает очень медленно с большим объемом данных, а потому непригоден для использования на практике, а пригоден лишь в обучающих и ознакомительных целях. Посмотрите на решения других задач по программированию.

Для вас это может быть интересно: