Алгоритм пузырьковой сортировки одномерного массива на 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;

}

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

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

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

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

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

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

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

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

Tima 13.09.2016

Везде о ней пишут, но по быстродействию она уступает любым другим. Напишите о QuickSort, будет полезно 🙂

Ответить ↓
1. Nicknixer Автор записи15.09.2016
  
  Да, действительно, по быстродействию она уступает многим другим. QuickSort в планах есть, в скором будущем.
  
  Ответить ↓
Безымянный 12.12.2016

А как отсортировать массив по возрастанию?

Ответить ↓
1. Марсель 30.05.2017
  
  if(mass[r] < mass[r+1])
  поменять здесь знак сравнения на противоположный
  
  Ответить ↓
Andrey 21.01.2017

ЭЭЭЭ
а разве можно объявлять int mas[n] ???
где n — это int n ??
в C++ статический массив объявляется только константой.

или так: int mas [10] например
или так:
const int n= 5;
int mas[n];

как у Вас это скомпилилось???

Ответить ↓
1. Николай Сергейчук Автор записи09.02.2017
  
  Можно, главное чтобы n было присвоено значение.
  
  Ответить ↓
2. ярослав 17.08.2017
  
  ПОЛНОСТЬЮ согласен
  
  Ответить ↓
Larisa 27.03.2017

У меня ваша программа не пошла. Пишет ошибки. Делала через Visual Studio

Ответить ↓
Larisa 27.03.2017

Работает только если в строку int mass вставить конкретное количество элементов

Ответить ↓
Larisa 27.03.2017

Согласна с Андреем.
Помогите, проверьте правильность строки int mass[n]

Ответить ↓
Larisa 27.03.2017

То есть в строке int mass[n] присвоить просто любое значение?
Тогда все идет. А почему, не пойму

Ответить ↓
1. Николай Сергейчук Автор записи27.03.2017
  
  Должно быть присвоено значение для переменной n до объявления массива.
  Например:
  int n =5;
  int mass[n];
  
  Ответить ↓
usa_rulit 13.04.2017

пишет что нужна константа в int mass[n];

Ответить ↓
usa_rulit 21.04.2017

почему бы во втором цикле не присваивать переменной 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;
}
}

}

Ответить ↓
Someone 04.08.2017

Ошибка в коде, ибо массив нужен динамический.
int n; // Кол-во элементов
cout <> n;
int *mass = new int[n];
Дальше уже можно писать, как на сайте, только в конце добавить delete [] mass;

Ответить ↓
иван 02.10.2017

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

Ответить ↓
RAISA 06.10.2018

спасибо!

Ответить ↓
Начинающий программист 14.11.2018

Здравствуйте! Пожалуйста сделайте программу которая сортирует одномерный массив пузырьком по столбцу.В инете никто не сделал это , похоже мало кто знает как вообще сделать.Я надеюсь на вас пожалуйста помогите мне с этим.

Ответить ↓
Scripted 15.12.2018

Просто в массив нельзя вставить «магическое число». Нужна константа. Либо как сказали выше — динамический массив.

Ответить ↓
slimshady 12.01.2020

код нифига не работает на с++

Ответить ↓