7.1 Пузырьковая сортировка

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


    Кроме пузырьковой сортировки к группе обменных относятся также быстрая сортировка и сортировка "расчёской". Следует отметить, что операция перестановки используется не только в алгоритмах обменной сортировки, но и во многих других.


    Описание алгоритма:
    Используются два цикла. Внешний проходится N − 1 раз, это гарантирует, что даже в худшем случае каждый элемент будет находиться на своем месте. В этом цикле устанавливается (смещается) граница между отсортированной и неотсортированной частями структуры данных. Во внутреннем цикле выполняются непосредственно операции сравнения и перестановки. Перестановка элементов производится методом "трёх вёдер:" содержимое первого элемента помещается в буферную переменную, на его место помещается содержимое второго элемента, на место которого помещается из буфера "старое" содержимое первого элемента. Количество проходов внутреннего цикла в каждом следующем проходе внешнего цикла уменьшается (от N − 1 до 1). Считается, что в среднем число проходов внутреннего цикла равно N/2. Процесс сортировки носит "треугольный" характер.

    Исходный массив d, c, a, b.
    В процессе работы программы массив будет изменяться следующим образом:

      d, c, a, b
      a, d, c, b
      a, b, d, c
      a, b, c, d

    Рассматриваемый вариант алгоритма всегда выполняет (N − 1)N/2 или (N2 − N)/2 (площадь треугольника) операций сравнения, так как внешний цикл выполняется N − 1 раз, а внутренний N/2.

    Число перестановок зависит от степени предварительной упорядоченности массива: В лучшем случае перестановки не выполняются (массив уже отсортирован в нужном направлении и число перестановок = 0);
    В среднем случае выполняется (N − 1)N/4 = (N2 − N)/4 перестановок (т.е. число сравнений пополам, число операций присваивания оказывается утроенным = 3(N − 1)N/4));
    В худшем случае (массив отсортирован в обратном направлении) выполняется (N − 1)N/2 = (N2 − N)/2 перестановок (или 3(N − 1)N/2 операций присваивания).

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





    Считается, что пузырьковая сортировка вообще является "учебной", но в реальности она может применяться для упорядочения массивов очень малого размера (3 − 7 элементов) в различных алгоритмах обработки сигналов.


    Процедура пузырьковой сортировки на языке "Паскаль"

    var
      str:array[0..M] of char;

    procedure bubble(item:array of char; n:integer);
    var
      a,b:integer;
      t:char;
    begin
      for a:=1 to n-1 do
        for b:=n-1 downto a do
          if item[b-1]>item[b] then
          begin
            {Перестановка}
            t:=item[b-1];
            item[b-1]:=item[b];
            item[b]:=t
          end
    end;

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

      d, c, a, b
      a, d, c, b
      a, b, d, c
      a, b, c, d


    procedure bubble1(item:array of char; n:integer);
    var
      a,ssign,pass:integer;
      t:char;
    begin
      ssign:=1;
      pass:=0;
      while ssign<>0 do
      begin
        ssign:=0;
        pass:=pass+1;
        for a:=0 to n-pass-1 do
          if item[a]>item[a+1] then
          begin
            t:=item[a-1];
            item[a-1]:=item[a];
            item[a]:=t;
            ssign:=1
          end
      end
    end;

    Аналогичные процедуры на языках Си/Си++

    void bubble(char* item,int n)
    {
      int a,b;
      char buf;
      for(a=1; a < n; ++a)
        for(b=n-1; b>=a; --b)
          if(item[b-1] > item[b])
          {
            buf=item[b-1];    // Перестановка
            item[b-1]=item[b];
            item[b]=buf;
          }
    }

    Вариант с условием Айверсона (перестановка не показана):

    void bubble1(char* item,int n)
    {
      int a,ssign=1,pass=0;
      char buf;
      while(ssign)
      {
        ssign=0;
        pass++;
        for(a=0; a < n-pass; a++)
          if(item[a] > item[a+1])
          {
            // Перестановка
            ssign++;
          }
    }

    Условие Айверсона является одной из попыток оптимизации этого алгоритма для повышения его эффективности, но обычно все такие попытки, включая ручную оптимизацию машинных команд, не приводят к заметному повышению скорости работы алгоритма.


    Существуют текстовые модификации приведённых процедуры, в которых, например, счётчики обоих циклов меняются на увеличение и т.п.


    Тип упорядоченности − по-возрастанию или по-убыванию − зависит от знака операции сравнения текущего и последующего элементов.


    < Назад | Вперед >

    Хостинг от uCoz