Наиболее известной (и наиболее "бесславной") является сортировка пузырьковым методом. Ее популярность объясняется запоминающимся названием и простотой алгоритма. Однако, эта сортировка является одной из самых худших среди всех когда-либо придуманных сортировок. Метод основан на том, что в процессе исполнения алгоритма более "легкие" элементы массива постепенно "всплывают". Особенностью данного метода является сравнение не каждого элемента со всеми, а сравнение в парах соседних элементов. Алгоритм пузырьковой сортировки по убыванию состоит в последовательных просмотрах снизу вверх (от начала к концу) массива М. Если соседние элементы таковы, что выполняется условие, согласно которому элемент справа больше элемента слева, то выполняется обмен значениями этих элементов.

Сортировка пузырьковым методом использует метод обменной сортировки. Она основана на выполнении в цикле операций сравнения и при необходимости обмена соседних элементов. Ее название происходит из-за подобия процессу движения пузырьков в резервуаре с водой, когда каждый пузырек находит свой собственный уровень. Ниже показана самая простая форма программы сортировки методом пузырька:

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

procedure Bubble (var item: DataArray; count: integer);

var

i,j: integer;

x: DataItem;

begin

for i: = 2 to count do

begin

for j: = count downto i do

if item [j-1] >item [j] then

begin

x: = item [j-1];

item [j-1]: = item [j];

item [j]: = x;

end;

end;

end; {конец сортировки пузырьковым методом}

В этом случае данное "item" является массивом элементов "DataItem", который сортируется, а данное "count" содержит число элементов в массиве.

Сортировка пузырьковым методом имеет два цикла. Поскольку число элементов массива задается переменной "count", внешний цикл вызывает просмотр массива count - 1 раз. Это обеспечивает нахождение каждого элемента в своей позиций после завершения процедуры. Внутренний цикл предназначен для фактического выполнения операций сравнения и обмена.

Для иллюстрации работы сортировки пузырьковым методом ниже даны результаты каждого этапа сортировки массива "dcab":

исходное положение: d c a b;

первый проход: a d c b;

второй проход: a b d c;

третий проход: a b c d.

При анализе всякой сортировки определяется число операций сравнения и обмена, выполняемых в лучшем, среднем и худшем случаях. Для сортировки пузырьковым методом число сравнений остается неизменным, поскольку два цикла всегда выполняются заданное число раз вне зависимости от упорядоченности исходного массива. Это означает, что при сортировке пузырьковым методом всегда выполняется 1/2 (n2-n) операций сравнения, где "n" задает число сортируемых элементов массива. Эта формула выводится на том основании, что внешний цикл сортировки пузырьковым методом выполняется n-1 раз, а внутренний цикл выполняется n/2 раз. Их перемножение даст указанную формулу. Число операций обмена будет нулевым для наилучшего случая, когда исходный массив уже является отсортированным. Число операций обмена для среднего случая будет равно 3/4 (n2-n), а для наихудшего случая будет равно 3/2 (n2-n) раз. Можно заметить, что по мере ухудшения упорядоченности исходного массива число неупорядоченных элементов приближается к числу сравнений (каждый неупорядоченный элемент требует три операции обмена). Сортировку пузырьковым методом называют квадратичным алгоритмом, поскольку время его выполнения пропорционально квадрату числа сортируемых элементов. Сортировка большого числа элементов пузырьковым методом потребует очень много времени, т.к. время выполнения сортировки находится в квадратичной зависимости от числа элементов массива. Например, если не учитывать время операций обмена, выполняемых для перестановки неупорядоченных элементов, то тогда при выполнении одной операции сравнения в течение 0,001 секунд сортировка десяти элементов займет 0,05 секунд, сортировка ста элементов займет 5 секунд, а сортировка 1000 элементов займет 500 секунд. Сортировка 100 000 элементов (такой размер имеет небольшой телефонный справочник) потребовала бы 5 000 000 секунд или около 1400 часов (т.е. два месяца непрерывной работы)! Сортировку пузырьковым методом можно в некоторой степени улучшить и тем самым немного улучшить ее временные характеристики. Можно, например, заметить, что сортировка пузырьковым методом обладает одной особенностью: расположенный не на своем месте в конце массива элемент (например, элемент "а" в массиве "dcab") достигает своего места за один проход, а элемент, расположенный в начале массива (например, элемент "d"), очень медленно достигает своего места. Необязательно все просмотры делать в одном направлении. Вместо этого всякий последующий просмотр можно делать в противоположном направлении. В этом случае сильно удаленные от своего места элементы будут быстро перемещаться в соответствующее место. Ниже показана улучшенная версия сортировки пузырьковым методом, получившая название "челночной сортировки" из-за соответствующего характера движений по массиву.

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

2.5 Сортировка выбором