131
правка
Изменения
→Модификации
== Псевдокод ==
Ниже приведен псевдокод сортировки пузырьком, на вход которой подается массив <tex> A[0..aA.size - 1] </tex>.
'''BubbleSort(A)'''
'''for''' i = 0 '''to''' a.size - 2:
if A[j] > A[j + 1]:
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''
