Метод пузырек для сортировки массива в С++

Часто приходится сортировать массивы. Метод пузырька самый просто и один из самых ресурсоемких.
Разберем работу на примере. Сортировать будем в порядке убывания:

Есть набор чисел 1 6 2 4 2 7 9
1)Сравниваем 1 и 6. 1 меньше 6 меняем местами. (6 1 2 4 7 9)
2)Сравниваем 1 и 2. 1 меньше 2 меняем местами. (6 2 1 4 7 9)
3)Сравниваем 1 и 4. 1 меньше 4 меняем местами. (6 2 4 1 7 9)
4)Сравниваем 1 и 7. 1 меньше 7 меняем местами. (6 2 4 7 1 9)
5)Сравниваем 1 и 9. 1 меньше 9 меняем местами. (6 2 4 7 9 1) Теперь следующий проход мы уже делаем с 5 первыми элементами. Так как меньший элемент найден.
6)Сравниваем 6 и 2. 6 больше 2 оставляем. (6 2 4 7 9 1)
7)Сравниваем 2 и 4. 2 меньше 4 меняем местами. (6 4 2 7 9 1)
8)Сравниваем 2 и 7. 2 меньше 7 меняем местами. (6 4 7 2 9 1)
9)Сравниваем 2 и 9. 2 меньше 9 меняем местами. (6 4 7 9 2 1) Проход закончен. Мы нашли 2 самое маленькое число. Следующий проход будет еще меньше.

15) Сравниваем 9 и 7. 9 больше 7 оставляем. (9 7 6 4 2 1) Все сортировка закончена.

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

Как видите, искомое число встает на свое место постепенно, как всплывающий пузырик в газировке. Отсюда и название.

Реализовать этот алгоритм можно так.
[php]
#include <iostream>
#include <fstream>
using namespace std;

int main()
{
const int n = 5;
int a[n];
ifstream f("file.txt");
for (int i = 0; i < n; ++i)
{
f >> a[i];
cout << a[i] << endl;
}
// soring
for (int i = n — 1; i >= 1; —i)
for (int j = 0; j < i; ++j)
{
if (a[j] > a[j + 1])
{
int foo = a[j];
a[j] = a[j + 1];
a[j + 1] = foo;
}
}
cout << endl;
for (int i = 0; i < n; ++i)
cout << a[i] << endl;
}
[/php]

1 Star2 Stars3 Stars4 Stars5 Stars (3 голосов, средний:5,00 из 5)
Вы можете пропустить чтение записи и оставить комментарий. Размещение ссылок запрещено.
Оставить комментарий