Методы сортировки в программировании: сортировка «пузырьком»

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

Откуда взялось такое необычное название?

сортировка пузырьком

Название метода придумали, используя аналогию с воздушными пузырьками в воде. Это метафора. Подобно тому, как маленькие пузыри воздуха поднимаются наверх — ведь их плотность больше, чем какой-либо жидкости (в данном случае — воды), так и каждый элемент массива, чем меньше он по значению, тем больше он постепенно пробирается к началу перечня чисел.

Описание алгоритма

Сортировка пузырьком выполняется следующим образом:

  • первый проход: элементы массива чисел берутся по два и также парами сравниваются. Если в какой-то двойке элементов первое значение оказывается больше второго, программа производит их обмен местами;
  • следовательно, наибольшее число попадает в конец массива. В то время как все остальные элементы остаются, как и были, в хаотичном порядке и требуют еще сортировки;
  • поэтому и необходим второй проход: производится он по аналогии с предыдущим (уже описанным) и имеет число сравнений — минус один;
  • у прохода номер три сравнений на единицу меньше, чем у второго, и на двойку, чем у первого. И так далее;
  • подытожим, что каждый проход имеет (всего значений в массиве, конкретное число) минус (номер прохода) сравнений.

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

Еще короче алгоритм будущей программы можно записать так:

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

Псевдокод на основе описанного алгоритма

Самая простая реализация выполняется так:

Процедура 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;

}.


Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *