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

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

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

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

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

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

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

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

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

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

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

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

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

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

}.


Внимание, только СЕГОДНЯ!

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