Участник: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].

Модификации

Сортировка чет-нечет - модификация пузырьковой сортировки, основанной на сравнении элементов стоящих на четных и нечетных позициях независимо друг от друга. Подробнее здесь - * http://en.wikipedia.org/wiki/Odd%E2%80%93even_sort Odd-even sort — Википедия]