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

Самый известный (и пользующийся дурной славой) алгоритм — пузырьковая сортировка (bubble sort, сортировка методом пузырька, или просто сортировка пузырьком)^[1]. Его популярность объясняется интересным названием и простотой самого алгоритма. Тем не менее, в общем случае это один из самых худших алгоритмов сортировки.

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

/* Пузырьковая сортировка. */
void bubble(char *items, int count)
{
  register int a, b;
  register char t;

  for(a=1; a < count; ++a)
    for(b=count-1; b >= a; --b) {
      if(items[b-1] > items[b]) {
        /* exchange elements */
        t = items[b-1];
        items[b-1] = items[b];
        items[b] = t;
      }
    }
}

Здесь items — указатель на массив символов, подлежащий сортировке, a count — количество элементов в массиве. Работа пузырьковой сортировки выполняется в двух циклах. Если количество элементов массива равно count, внешний цикл приводит к просмотру массива count - 1 раз. Это обеспечивает размещение элементов в правильном порядке к концу выполнения функции даже в самом худшем случае. Все сравнения и обмены выполняются во внутреннем цикле. (Слегка улучшенная версия алгоритма пузырьковой сортировки завершает работу, если при просмотре массива не было сделано ни одного обмена, но это достигается за счет добавления еще одного сравнения при каждом проходе внутреннего цикла.)

С помощью этой версии алгоритма пузырьковой сортировки можно сортировать массивы символов по возрастанию. Например, следующая короткая программа сортирует строку, вводимую пользователем:

/* Программа, вызывающая функцию сортировки bubble */

#include <string.h>
#include <stdio.h>
#include <stdlib.h>

void bubble(char *items, int count);

int main(void)
{
  char s[255];

  printf("Введите строку:");
  gets(s);
  bubble(s, strlen(s));
  printf("Отсортированная строка: %s.\n", s);

  return 0;
}

Чтобы наглядно показать, как работает пузырьковая сортировка, допустим, что исходный массив содержит элементы dcab. Ниже показано состояние массива после каждого прохода:

Начало       d c a b
Проход 1     a d c b
Проход 2     a b d c
Проход 3     a b c d

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

В пузырьковой сортировке количество сравнений всегда одно и то же, поскольку два цикла for повторяются указанное количество раз независимо от того, был список изначально упорядочен или нет. Это значит, что алгоритм пузырьковой сортировки всегда выполняет

(n²-n)/2

сравнений, где n — количество сортируемых элементов. Данная формула выведена на том основании, что внешний цикл выполняется n - 1 раз, а внутренний выполняется в среднем n/2 раз. Произведение этих величин и дает предыдущее выражение.

Обратите внимание на член n² в формуле. Говорят, что пузырьковая сортировка является алгоритмом порядка n², поскольку время ее выполнения пропорционально квадрату количества сортируемых элементов. Необходимо признать, что алгоритм порядка n² не эффективен при большом количестве элементов, поскольку время выполнения растет экспоненциально в зависимости от количества сортируемых элементов. На рис. 21.1 показан график роста времени сортировки с увеличением размера массива.

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

Рис. 21.1. Время сортировки порядка n² в зависимости от размера массива. (На самом деле здесь нарисована кривая у=n²/1000, а не кривая у=n², крутизна которой в 1000 раз выше. Фактически это все равно, что нарисовать кривую у=n², выбрав по оси ординат более мелкий масштаб (в 1000 раз). Начертить кривую у=n² без растяжения вдоль оси абсцисс, на которой откладываются значения n, практически невозможно. Дело в том, что при выбранном интервале изменения n (от 0 до 1000) кривая у=n² практически сливается с осью ординат.)

Алгоритм пузырьковой сортировки можно немного улучшить, если попытаться повысить скорость его работы. Например, пузырьковая сортировка имеет такую особенность: неупорядоченные элементы на "большом" конце массива (например, "а" в примере dсаb) занимают правильные положения за один проход, но неупорядоченные элементы в начале массива (например, "d") поднимаются на свои места очень медленно. Этот факт подсказывает способ улучшения алгоритма. Вместо того чтобы постоянно просматривать массив в одном направлении, в последовательных проходах можно чередовать направления. Этим мы добьемся того, что элементы, сильно удаленные от своих положений, быстро станут на свои места. Данная версия пузырьковой сортировки носит название шейкер-сортировки (shaker sort)^[2], поскольку действия, производимые ею с массивом, напоминают взбалтывание или встряхивание. Ниже показана реализация шейкер-сортировки.

/* Шейкер-сортировка. */
void shaker(char *items, int count)
{
  register int a;
  int exchange;
  char t;

  do {
    exchange = 0;
    for(a=count-1; a > 0; --a) {
      if(items[a-1] > items[a]) {
        t = items[a-1];
        items[a-1] = items[a];
        items[a] = t;
        exchange = 1;
      }
    }

    for(a=1; a < count; ++a) {
      if(items[a-1] > items[a]) {
        t = items[a-1];
        items[a-1] = items[a];
        items[a] = t;
        exchange = 1;
      }
    }
  } while(exchange); /* сортировать до тех пор, пока не будет обменов */
}

Хотя шейкер-сортировка и является улучшенным вариантом по сравнению с пузырьковой сортировкой, она по-прежнему имеет время выполнения порядка n². Это объясняется тем, что количество сравнений не изменилось, а количество обменов уменьшилось лишь на относительно небольшую константу. Шейкер-сортировка лучше пузырьковой, но есть еще гораздо лучшие алгоритмы сортировки.

^[1]На самом деле есть даже два алгоритма пузырьковой сортировки: сортировка пузырьковым вьючением и сортировка пузырьковой выборкой. Впрочем, эффективность обоих одинакова.

^[2]А также сортировки перемешиванием (cocktail shaker sort), сортировки взбалтыванием, сортировки встряхиванием. Как бы то ни было, это вид пузырьковой сортировки, в которой альтернативные проходы выполняются в противоположном направлении.