Сортировка пузырьком не только не считается самым быстрым методом, более того, она замыкает перечень самых медленных способов упорядочивания. Однако и у нее есть свои плюсы. Так, сортировка методом пузырька - самое что ни на есть логичное и естественное решение проблемы, если необходимо расставить элементы в определенном порядке. Обычный человек вручную, к примеру, воспользуется именно им - просто по интуиции.
Откуда взялось такое необычное название?
Название метода придумали, используя аналогию с воздушными пузырьками в воде. Это метафора. Подобно тому, как маленькие пузыри воздуха поднимаются наверх - ведь их плотность больше, чем какой-либо жидкости (в данном случае - воды), так и каждый элемент массива, чем меньше он по значению, тем больше он постепенно пробирается к началу перечня чисел.
Описание алгоритма
Сортировка пузырьком выполняется следующим образом:
- первый проход: элементы массива чисел берутся по два и также парами сравниваются. Если в какой-то двойке элементов первое значение оказывается больше второго, программа производит их обмен местами;
- следовательно, наибольшее число попадает в конец массива. В то время как все остальные элементы остаются, как и были, в хаотичном порядке и требуют еще сортировки;
- поэтому и необходим второй проход: производится он по аналогии с предыдущим (уже описанным) и имеет число сравнений - минус один;
- у прохода номер три сравнений на единицу меньше, чем у второго, и на двойку, чем у первого. И так далее;
- подытожим, что каждый проход имеет (всего значений в массиве, конкретное число) минус (номер прохода) сравнений.
Еще короче алгоритм будущей программы можно записать так:
- массив чисел проверяется до тех пор, пока не будут найдены какие-либо два числа, причем второе из них обязано быть больше первого;
- неправильно расположенные по отношению друг к другу элементы массива программа меняет местами.
Псевдокод на основе описанного алгоритма
Самая простая реализация выполняется так:
Процедура Sortirovka_Puzirkom;
Начало
цикл для j от nachalnii_index до konechii_index;
цикл для i от nachalnii_index до konechii_index-1;
если massiv[i]>massiv[i+1] (первый элемент больше второго), то:
(меняем значения местами);
Конец
Конечно, здесь простота только усугубляет ситуацию: чем проще алгоритм, тем более в нем проявляются все недостатки. Затратность времени слишком велика даже для небольшого массива (тут вступает в дело относительность: для обывателя количество времени может казаться маленьким, но в деле программиста каждая секунда или даже миллисекунда на счету).
Потребовалась реализация получше. Например, учитывающая обмен значений в массиве местами:
Процедура Sortirovka_Puzirkom;
Начало
sortirovka = истина;
цикл пока sortirovka = истина;
sortirovka = ложь;
цикл для i от nachalnii_index до konechii_index-1;
если massiv[i]>massiv[i+1] (первый элемент больше второго), то:
(меняем элементы местами);
sortirovka = истина; (обозначили, что обмен был произведен).
Конец.
Недостатки метода
Основной минус - продолжительность процесса. Сколько же времени выполняется алгоритм сортировки пузырьком?
Время выполнения рассчитывается из квадрата количества чисел в массиве - конечный результат ему пропорционален.
При наихудшем варианте массив будет пройден столько же раз, сколько в нем имеется элементов минус одно значение. Так происходит потому, что в конечном итоге остается только один элемент, который не с чем сравнивать, и последний проход по массиву становится бесполезным действом.
Кроме того, эффективен метод сортировки простыми обменами, как его еще называют, только для массивов небольшого размера. Большие объемы данных с его помощью обработать не получится: результатом станут либо ошибки, либо сбой работы программы.
Достоинства
Сортировка пузырьком весьма проста для понимания. В учебных программах технических ВУЗов при изучении упорядочивания элементов массива ее проходят в первую очередь. Метод легко реализуется как на языке программирования Delphi (Д (Делфи), так и на C/C++ (Си/Си плюс плюс), невероятно простой алгоритм расположения значений в верном порядке и на Pascal (Паскаль). Сортировка пузырьком идеально подходит для начинающих.
По причине недостатков алгоритм не применяют во внеучебных целях.
Наглядный принцип сортировки
Изначальный вид массива 8 22 4 74 44 37 1 7
Шаг 1 8 22 4 74 44 37 1 7
8 22 4 74 44 1 37 7
8 22 4 74 1 44 37 7
8 22 4 1 74 44 37 7
8 22 1 4 74 44 37 7
8 1 22 4 74 44 37 7
1 8 22 4 74 44 37 7
Шаг 2 1 8 22 4 74 44 7 37
1 8 22 4 74 7 44 37
1 8 22 4 7 74 44 37
1 8 22 4 7 74 44 37
1 8 4 22 7 74 44 37
1 4 8 22 7 74 44 37
Шаг 3 1 4 8 22 7 74 37 44
1 4 8 22 7 37 74 44
1 4 8 22 7 37 74 44
1 4 8 7 22 37 74 44
1 4 7 8 22 37 74 44
Шаг 4 1 4 7 8 22 37 44 74
1 4 7 8 22 37 44 74
1 4 7 8 22 37 44 74
1 4 7 8 22 37 44 74
Шаг 5 1 4 7 8 22 37 44 74
1 4 7 8 22 37 44 74
1 4 7 8 22 37 44 74
Шаг 6 1 4 7 8 22 37 44 74
1 4 7 8 22 37 44 74
Шаг 7 1 4 7 8 22 37 44 74
Пример сортировки пузырьком на языке Pascal
Пример:
const kol_mas=10;
var massiv:array[1..kol_mas] of integer;
a, b, k: integer;
begin
writeln ('input', kol_mas, 'elements of array');
for a:=1 to kol_mas do readln( massiv[a] );
for a:=1 to kol_mas-1 do begin
for b:=a+1 to kol_mas do begin
if massiv[a]>massiv[b] then begin
k:=massiv[a]; massiv[a]:=massiv[b]; massiv[b]:=k;
end;
end;
end;
writeln ('after sort');
for a:=1 to kol_mas do writeln( massiv[a] );
end.
Пример сортировки пузырьком на языке С (Си)
Пример:
#include
#include
int main(int argc, char* argv[])
{
int massiv[8] = {36, 697, 73, 82, 68, 12, 183, 88},i, ff;
for (; ;){
ff = 0;
for (i = 7; i>0; i--){
if (massiv[i] < massiv[i-1]) {
swap (massiv[i],massiv[i-1]);
ff++;
}
}
if (ff == 0) break;
}
getch(); // задержка экрана
return 0;
}.
