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

Материал из Викиконспекты
Перейти к: навигация, поиск

Сортировка простыми обменами, сортировка пузырьком (англ. bubble sort) — один из квадратичных алгоритмов сортировки.

Алгоритм

Алгоритм состоит в повторяющихся проходах по сортируемому массиву. На каждой итерации последовательно сравниваются соседние элементы, и, если порядок в паре неверный, то элементы меняют местами. За каждый проход по массиву как минимум один элемент встает на свое место, поэтому необходимо совершить не более [math] n - 1 [/math] проходов, где [math] n [/math] размер массива, чтобы отсортировать массив.

Псевдокод

Ниже приведен псевдокод сортировки пузырьком, на вход которой подается массив [math] A[0..n - 1] [/math].

 bubbleSort(A):
   for i = 0 to n - 2
     for j = 0 to n - 2
       if A[j] > A[j + 1]
         swap(A[j], A[j + 1])

Оптимизация

  • Можно заметить, что после [math] i [/math]-ой итерации внешнего цикла [math] i [/math] последних элементов уже находятся на своих местах в отсортированном порядке, поэтому нет необходимости производить их сравнения друг с другом. Следовательно, внутренний цикл можно выполнять не до [math] n - 2 [/math], а до [math] n - i - 2 [/math].
  • Также заметим, что если после выполнения внутреннего цикла не произошло ни одного обмена, то массив уже отсортирован, и продолжать что-то делать бессмысленно. Поэтому внутренний цикл можно выполнять не [math] n - 1 [/math] раз, а до тех пор, пока во внутреннем цикле происходят обмены.

При использовании первой оптимизации сортировка принимает следующий вид:

 bubbleSort(A):
   for i = 0 to n - 2
     for j = 0 to n - i - 2
       if A[j] > A[j + 1]
         swap(A[j], A[j + 1])

При использовании же обеих оптимизаций сортировка пузырьком выглядит так:

 bubbleSort(A):
   i = 0
   t = true
   while t
     t = false
     for j = 0 to n - i - 2
       if A[j] > A[j + 1]
         swap(A[j], A[j + 1])
         t = true;
     i = i + 1

Сложность

В данной сортировке выполняются всего два различных вида операции: сравнение элементов и их обмен. Поэтому время всего алгоритма [math] T = T_1 + T_2 [/math], где [math] T_1 [/math] — время, затрачиваемое на сравнение элементов, а [math] T_2 [/math] — время, за которое мы производим все необходимые обмены элементов.

Так как в алгоритме меняться местами могут только соседние элементы, то каждый обмен уменьшает количество инверсий на единицу. Следовательно, количество обменов равно количеству инверсий в исходном массиве вне зависимости от реализации сортировки. Максимальное количество инверсий содержится в массиве, элементы которого отсортированы по убыванию. Несложно посчитать, что количество инверсий в таком массиве [math] \frac {n (n - 1)} {2} [/math]. Получаем, что [math] T_2 = O(n^2) [/math].

В неоптимизированной реализации на каждой итерации внутреннего цикла производятся [math] n - 1 [/math] сравнений, а так как внутренний цикл запускается также [math] n - 1 [/math] раз, то за весь алгоритм сортировки производятся [math] (n - 1)^2 [/math] сравнений.

В оптимизированной версии точное количество сравнений зависит от исходного массива. Известно, что худший случай равен [math] \frac {n (n - 1)} {2} [/math], а лучший — [math] n-1 [/math]. Следовательно, [math] T_1 = O(n^2) [/math].

В итоге получаем [math] T = T_1 + T_2 = O(n^2) + O(n^2) = O(n^2) [/math].

Пример работы алгоритма

Возьмём массив с числами «5 1 4 2 8» и отсортируем значения по возрастанию, используя сортировку пузырьком. Выделены те элементы, которые сравниваются на данном этапе.


Первый проход:

До После Описание шага
5 1 4 2 8 1 5 4 2 8 Здесь алгоритм сравнивает два первых элемента и меняет их местами.
1 5 4 2 8 1 4 5 2 8 Меняет местами, так как 5 > 4
1 4 5 2 8 1 4 2 5 8 Меняет местами, так как 5 > 2
1 4 2 5 8 1 4 2 5 8 Теперь, ввиду того, что элементы стоят на своих местах (8 > 5), алгоритм не меняет их местами.

Второй проход:

До После Описание шага
1 4 2 5 8 1 4 2 5 8
1 4 2 5 8 1 2 4 5 8 Меняет местами, так как 4 > 2
1 2 4 5 8 1 2 4 5 8
1 2 4 5 8 1 2 4 5 8

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

Модификации

Сортировка чет-нечет (англ. odd-even sort) — модификация пузырьковой сортировки, основанной на сравнении элементов стоящих на четных и нечетных позициях независимо друг от друга. Сложность — [math] O(n^2) [/math]. Псевдокод указан ниже:

odd-even_sort(a):
for (i = 0 to n-1 step 1)
    if i mod 2 =0
         for (j = 2 to n-1 step 2)
             if (a[j] < a[j-1])
                 swap(a[j-1], a[j]))  
    else      
         for (j = 1 to n-1 step 2)
             if a[j] < a[j-1]
                 swap(a[j-1], a[j])

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


Сортировка расческой (англ. comb sort) — модификация пузырьковой сортировки, основанной на сравнении элементов на расстоянии. Сложность —[math] O(n^2) [/math], но стремится к [math] O(n(log(n)) [/math]. Является самой быстрой квадратичной сортировкой. Недостаток — она неустойчива. Псевдокод указан ниже

combsort(a):
      k =1.24733
      jump = n
      bool swapped = true;
      while (jump > 1 and swapped) 
          if (jump > 1)
              jump /= k;
          swapped = false;
          for ( i = 0; i + jump < size; ++i)
              if a[i + jump]< array[i]) 
                  swap(array[i], array[i + jump]);
                  swapped = true;

Пояснения: Изначально расстояние между сравниваемыми элементами равно [math] n/k [/math], где k =1.24733 — оптимальное число для этого алгоритма. Сортируем массив по этому k, потом уменьшаем его по этому же правилу. Когда k достигает единицы, массив досортировывается обычным пузырьком.

Сортировка перемешиванием (англ. cocktail sort), также известная как Шейкерная сортировка — разновидность пузырьковой сортировки, сортирующая массив в 2 направлениях на каждой итерации. В среднем, сортировка перемешиванием работает в 2 раза быстрее пузырька. Сложность — [math] O(n^2) [/math], но стремится она к [math] O(k*n) [/math], где k — максимальное расстояние элемента в неотсортированном массиве от его позиции в отсортированном массиве.

См. также

Ссылки