Изменения

== Псевдокод ==Ниже приведен псевдокод сортировки пузырьком, на вход которой подается массив <tex> Aa[0..n - 1] </tex>. '''function''' bubbleSort(Aa): '''for''' i = 0 '''to''' n - 2 '''for''' j = 0 '''to''' n - 2 '''if''' Aa[j] > Aa[j + 1] swap(Aa[j], Aa[j + 1])

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

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

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

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

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

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

 === Сортировка чет-нечет ==='''Сортировка чет-нечет''' (англ. ''odd-even sort'') {{---}} модификация пузырьковой сортировки, основанной основанная на сравнении элементов стоящих на четных и нечетных позициях независимо друг от друга. Сложность {{---}} <tex> O(n^2) </tex>.

'''function''' oddevensortoddEvenSort(a): '''for''' (i = 0 '''to n-1 ''step'' n - 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]))

'''for''' (j = 1 '''to ''' n-1 '''step''' 2) '''if''' a[j] < a[j-1] swap(a[j-1], a[j])

'''Сортировка расческой''' (англ. ''comb sort'') {{---}} модификация пузырьковой сортировки, основанной на сравнении элементов на расстоянии. Сложность {{---}}<tex> O(n^2) </tex>, но стремится к <tex> O(n \log n) </tex>. Является самой быстрой квадратичной сортировкой. Недостаток {{---}} она неустойчива. Псевдокод указан ниже '''function''' combsortcombSort(a): k =1.3 jump = n '''bool''' swapped = ''true'' '''while''' jump > 1 '''and ''' swapped) '''if ''' jump > 1 jump /= k swapped = ''false;'' '''for''' ( i = 0; i + '''to''' size - jump < size; ++i)- 1 '''if''' a[i + jump]< arraya[i] swap(arraya[i], arraya[i + jump]) swapped = ''true''Пояснения: Изначально расстояние между сравниваемыми элементами равно <texdpi=150> \frac{n/}{k } </tex>, где <tex> k =1{.}3 </tex> {{---}} оптимальное число для этого алгоритма. Сортируем массив по этому расстоянию, потом уменьшаем его по этому же правилу. Когда расстояние между сравниваемыми элементами достигает единицы, массив досортировывается обычным пузырьком. '''Сортировка перемешиванием '''(англ. ''cocktail sort''), также известная как '''Шейкерная сортировка''' {{---}} разновидность пузырьковой сортировки, сортирующая массив в двух направлениях на каждой итерации. В среднем, сортировка перемешиванием работает в два раза быстрее пузырька. Сложность {{---}} <tex> O(n^2) </tex>, но стремится она к <tex> O(k \cdot n) </tex>, где k {{---}} максимальное расстояние элемента в неотсортированном массиве от его позиции в отсортированном массиве. Псевдокод указан ниже:

=== Сортировка перемешиванием Shakersort==='''Сортировка перемешиванием''' (англ. ''cocktail sort''), также известная как '''Шейкерная сортировка''' {{---}} разновидность пузырьковой сортировки, сортирующая массив в двух направлениях на каждой итерации. В среднем, сортировка перемешиванием работает в два раза быстрее пузырька. Сложность {{---}} <tex> O(n^2) </tex>, но стремится она к <tex> O(k \cdot n) </tex>, где <tex> k </tex> {{---}} максимальное расстояние элемента в неотсортированном массиве от его позиции в отсортированном массиве. Псевдокод указан ниже:

'''forfunction''' shakerSort(int i a): begin = -1 end = 0; i < n/- 2; i++) '''while''' swapped beg swapped = 0;''false'' end = n - 1;begin++ '''whilefor''' beg<i =begin '''to''' end do '''if''' a[begi] >a[beg i + 1] Swap swap(a[begi],a[begi +1]); swapped = ''true'' '''if''' !swapped '''break''' beg++ swapped = ''false'' end-- '''for''' i = end '''downto''' begin '''if''' a[end-1i] > a[endi + 1] Swap swap(a[end - 1i], a[endi + 1]); end--; swapped = ''true''

== Ссылки Источники информации ==* [http://en.wikipedia.org/wiki/Bubble_sort Сортировка пузырьком — {{---}} Википедия]

* [http://en.wikipedia.org/wiki/Odd%E2%80%93even_sort Сортировка чет-нечет {{- --}} Википедия]* [http://en.wikipedia.org/wiki/Comb_sort Сортировка расческой {{--- }} Википедия]* [http://en.wikipedia.org/wiki/Cocktail_sort Сортировка перемешиванием{{--- }} Википедия]

[[Категория: СортировкиСортировка]][[Категория: Квадратичные сортировки]]