swap(A[j], A[j + 1]);
В оптимизированной версии Для первой оптимизации точное количество сравнений зависит от исходного массива и в хуйдшем худшем случае составляет <tex>\displaystyle \frac {n(n - 1)} {2}</tex>. Следовательно, <tex> T_1 = O(n^2) </tex>. == Модификации ==[http://en.wikipedia.org/wiki/Odd%E2%80%93even_sort Сортировка чет-нечет] - модификация пузырьковой сортировки, основанной на сравнении элементов стоящих на четных и нечетных позициях независимо друг от друга. [http://en.wikipedia.org/wiki/Comb_sort Сортировка расческой] - модификация пузырьковой сортировки, основанной на сравнении элементов на расстоянии. По мере упорядочивания массива это расстояние уменьшается и как только оно достигает 1, массив "досортировывается" обычным пузырьком. Сложность - <tex> O(nlog(n)) </tex>.'''Шаг 1''' мы вычисляем k которое равно [http://en.wikipedia.org/wiki/Cocktail_sort Сортировка перемешиванием] - разновидность пузырьковой сортировки, сортирующая массив в 2 направлениях на каждой итерации. В среднем, сортировка перемешиванием работает в 2 раза быстрее пузырька. Сложность - <tex> O(N^2) </tex>. В оптимизированной версии точное количество сравнений зависит от исходного массива. Но точно известно, что их количество не меньше, чем количество обменов, и не больше, чем <tex> (n - 1)^2 </tex> {{---}} максимальное количество сравнений для данной сортировки. Следовательно, <tex> T_1 = O(n^2) </tex>. 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]); combsort(a): jump = n bool swapped = true; while (jump > 1 '''and''' swapped) if (jump > 1) jump /= 1.24733; swapped = false; for ( i = 0; i + jump < size; ++i) if a[i + jump]< array[i]) swap(array[i], array[i + jump]); swapped = true; '''function''' shakerSort: begin = -1 end = n - 2 '''while''' swapped swapped = ''false'' begin++ '''for''' i= begin to end '''if''' A[i] > A[i+1] swap(A[i],A[i+1]) swapped = ''true'' '''if''' swapped = false '''break''' swapped = ''false'' end = end - 1 '''for''' i = end '''downto''' begin '''if''' A[i]>A[i+1] swap(A[i],A[i+1]) swapped = ''true''
