243
правки
Изменения
объединены разделы "Алгоритм" и "Псевдокод"; отступы, пробелы после тире, равно и т.п., исправление орфографических ошибок
Алгоритм состоит в повторяющихся проходах по сортируемому массиву. На каждой итерации последовательно сравниваются соседние элементы, и, если порядок в паре неверный, то элементы меняют местами. За каждый проход по массиву как минимум один элемент встает на свое место, поэтому необходимо совершить не более <tex> n - 1 </tex> проходов, где <tex> n </tex> размер массива, чтобы отсортировать массив.
Ниже приведен псевдокод сортировки пузырьком, на вход которой подается массив <tex> a[0..n - 1] </tex>.
'''function''' bubbleSort(a):
При использовании первой оптимизации сортировка принимает следующий вид:
'''function''' bubbleSort(a):
При использовании же обеих оптимизаций сортировка пузырьком выглядит так:
'''function''' bubbleSort(a):
== Сложность ==
|}
Теперь массив полностью отсортирован, но неоптимизированный алгоритм проведет еще два прохода, на которых ничего не изменится, в отличии отличие от алгоритма, использующего вторую оптимизацию, который сделает один проход и прекратит свою работу, так как не сделает за этот проход ни одного обмена.
== Модификации ==
'''function''' oddEvenSort(a):
'''for''' i = 0 '''to''' n - 1
Преимущество этой сортировки {{---}} на нескольких процессорах она выполняется быстрее, так как четные и нечетные индексы сортируются параллельно.
=== Сортировка расческой ===
'''Сортировка расческой''' (англ. ''comb sort'') {{---}} модификация пузырьковой сортировки, основанной на сравнении элементов на расстоянии. Сложность {{---}}<tex> O(n^2) </tex>, но стремится к <tex> O(n \log n) </tex>. Является самой быстрой квадратичной сортировкой. Недостаток {{---}} она неустойчива. Псевдокод указан ниже:
=== Сортировка перемешиванием ===
'''Сортировка перемешиванием''' (англ. ''cocktail sort''), также известная как '''Шейкерная сортировка''' {{---}} разновидность пузырьковой сортировки, сортирующая массив в двух направлениях на каждой итерации. В среднем, сортировка перемешиванием работает в два раза быстрее пузырька. Сложность {{---}} <tex> O(n^2) </tex>, но стремится она к <tex> O(k \cdot n) </tex>, где <tex> k </tex> {{---}} максимальное расстояние элемента в неотсортированном массиве от его позиции в отсортированном массиве. Псевдокод указан ниже:
== См. также ==
