Операция сравнения/перестановки выполняется для каждых двух стоящих 
рядом элементов. После первого прохода по массиву "вверху" оказывается
самый "легкий" элемент. Следующий цикл сортировки выполняется начиная 
со второго элемента, в результате чего вторым в массиве оказывается 
второй наименьший по величине элемент, и так далее.

{ Сортируются записи типа item по ключу item.key }
{ для вспомогательных переменных используется тип index }
procedure BubbleSort;
    var i,j: index; x:item;
begin for i:=2 to n do
    begin for j:=n downto i do
	    if a[j-1].key > a[j].key then
		begin x:=a[j-1]; a[j-1]:=a[j]; a[j]:=x;
		end;
	end;
end;

  Пример 1. Проходим по массиву снизу вверх. Меньшие/более легкие/
            элементы 'всплывают' наверх, давая название методу.
  
  Hачальные  i      i      i      i      i      i      i
    ключи    2      3      4      5      6      7      8
     44 /-> 06     06     06     06     06     06     06   
     55 |   44 /-> 12     12     12     12     12     12
     12 |   55 |   44 /-> 18     18     18     18     18
     42 |   12-/   55 |   44 /-> 42     42     42     42
     94 |   42 /-> 18-/   55 |   44 --> 44     44     44
     18 |   94 |   42     42-/   55     55 --> 55     55
     06-/   18-/   94 ->  67     67     67     67 --> 67
     67     67     67-/   94     94     94     94     94
	 	 
 Алгоритм пузырька очень медленен и неэффективен. Тем не менее,
у него есть громадный плюс: он прост и его можно по-всякому улучшать.
Чем мы сейчас и займемся.

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

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

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

  Hапример, массив 12 18 42 44 55 67 94 06 будет отсортирован за 1 проход,
а сортировка массива 94 06 12 18 42 44 55 67 потребует 7 проходов.

Эта неестественная асимметрия подсказывает третье улучшение:
менять направление следующих один за другим проходов.
Получившийся алгоритм иногда называют 'шейкер-сортировкой'.

  Пример его работы на том же входном массиве.
	
         l  =  2       3       3       4       4
         r  =  8       8       7       7       4
              44  /-> 06      06      06      06
              55  |   44      44  /-> 12      12
              12  |   55 -\   12 -/   44 -\   18
              42  |   12  |   42  /-> 18  |   42
              94  |   42  \-> 55  |   42  \-> 44
              18  |   94 -\   18 -/   55      55
              06 -/   18  |   67      67      67
              67      67  \-> 94      94      94
 Проходы:     /|\      |      /|\      |      /|\
               |      \|/      |      \|/      |
			   
			   
procedure ShakerSort;
    var j,k,l,r: index; x: item;
begin l:=2; r:=n; k:=n;
    repeat
	    for j:=r downto l do
		    if a[j-1].key > a[j].key then
			begin x:=a[j-1]; a[j-1]:=a[j]; a[j]:=x;
                k:=j;
			end;
		l:=k+1;
		for j:=l to r do
		    if a[j-1].key > a[j].key then
			begin x:=a[j-1]; a[j-1]:=a[j]; a[j]:=x;
			    k:=j;
			end;
		r:=k-1;
	until l>r;
end;
			   
Анализ алгоритма простого пузырька:
  Число сравнений   
    C = 1/2 (n^2 - n),
 Числа пересылок:
   Mmin = 0, Mсреднее = 3/4 (n^2 - n), Mmax = 3/2 (n^2 - n).             
			   
Анализ шейкер-сортировки (из книги Д.Кнута):	 
  Минимальное число сравнений Cmin = n-1
  Среднее число проходов пропорционально n - k1*корень(n),
  Cреднее число сравнений пропорционально 1/2 ( n^2 - n(k2+ln(n)) ).
  
Hо, как видно, все предложенные усовершенствования не влияют на число 
обменов. К сожалению, обмен - операция, как правило, гораздо более 
медленная, чем сравнение ключей, поэтому реальный эффект улучшений
гораздо меньше, чем можно было бы ожидать.

  Метод пузырька и описанные улучшения на практике крайне неэффективны,
SelectSort и InsertSort работают быстрее. Шейкер-сортировку выгодно
использовать, когда известно, что элементы уже почти упорядочены.
Hо даже в этом случае обычно применяют все же InsertSort, которая
менее чувствительна к степени упорядоченности.