Участник:Satosik

Псевдокод

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

 BubbleSort(A)
   for i = 0 to a.size - 2:
     for j = 0 to a.size - 2:
       if A[j] > A[j + 1]:
         swap(A[j], A[j + 1]);

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

Модификации

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

Сортировка расческой - модификация пузырьковой сортировки, основанной на сравнении элементов на расстоянии. По мере упорядочивания массива это расстояние уменьшается и как только оно достигает 1, массив "досортировывается" обычным пузырьком. Сложность - [math] O(nlog(n)) [/math].

Сортировка перемешиванием - разновидность пузырьковой сортировки, сортирующая массив в 2 направлениях на каждой итерации. В среднем, сортировка перемешиванием работает в 2 раза быстрее пузырька. Сложность - [math] O(N^2) [/math].

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

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