Изменения

'''Алгоритм сортировкиСортировка простыми обменами''', '''сортировка пузырьком''' — это алгоритм для упорядочивания элементов(англ. Поле, служащее критерием порядка, называется ключом ''bubble sort'') — один из квадратичных алгоритмов сортировки. На практике в качестве ключа часто выступает число, а в остальных полях хранятся какие-либо данные, никак не влияющие на работу алгоритма.

== Алгоритм ==Алгоритм состоит в повторяющихся проходах по сортируемому массиву. На каждой итерации последовательно сравниваются соседние элементы, и, если порядок в паре неверный, то элементы меняют местами. За каждый проход по массиву как минимум один элемент встает на свое место, поэтому необходимо совершить не более <tex> n - 1 </tex> проходов, где <tex> n </tex> размер массива, чтобы отсортировать массив. Ниже приведен псевдокод сортировки пузырьком, на вход которой подается массив <tex> a[0..n - 1] </tex>. '''function''' bubbleSort(a): '''for''' i = 0 '''to''' n - 2 '''for''' j = 0 '''to''' n - 2 '''if''' a[j] > a[j + 1] swap(a[j], a[j + 1]) == Оптимизация ==* Можно заметить, что после <tex> i </tex>-ой итерации внешнего цикла <tex> i </tex> последних элементов уже находятся на своих местах в отсортированном порядке, поэтому нет необходимости производить их сравнения друг с другом. Следовательно, внутренний цикл можно выполнять не до <tex> n - 2 </tex>, а до <tex> n - i - 2 </tex>.* Также заметим, что если после выполнения внутреннего цикла не произошло ни одного обмена, то массив уже отсортирован, и продолжать что-то делать бессмысленно. Поэтому внутренний цикл можно выполнять не <tex> n - 1 </tex> раз, а до тех пор, пока во внутреннем цикле происходят обмены. При использовании первой оптимизации сортировка принимает следующий вид: '''function''' bubbleSort(a): '''for''' i = 0 '''to''' n - 2 '''for''' j = 0 '''to''' n - i - 2 '''if''' a[j] > a[j + 1] swap(a[j], a[j + 1]) При использовании же обеих оптимизаций сортировка пузырьком выглядит так: '''function''' bubbleSort(a): i = 0 t = ''true'' '''while''' t t = ''false'' '''for''' j = 0 '''to''' n - i - 2 '''if''' a[j] > a[j + 1] swap(a[j], a[j + 1]) t = ''true'' i = i + 1 == Сложность ==В данной сортировке выполняются всего два различных вида операции: сравнение элементов и их обмен. Поэтому время всего алгоритма <tex> T = T_1 + T_2 </tex>, где <tex> T_1 </tex> {{---}} время, затрачиваемое на сравнение элементов, а <tex> T_2 </tex> {{---}} время, за которое мы производим все необходимые обмены элементов. Так как в алгоритме меняться местами могут только соседние элементы, то каждый обмен уменьшает количество [[Таблица инверсий|инверсий]] на единицу. Следовательно, количество обменов равно количеству инверсий в исходном массиве вне зависимости от реализации сортировки. Максимальное количество инверсий содержится в массиве, элементы которого отсортированы по убыванию. Несложно посчитать, что количество инверсий в таком массиве <tex dpi=150> \frac {n (n - 1)} {2} </tex>. Получаем, что <tex> T_2 = O(n^2) </tex>. В неоптимизированной реализации на каждой итерации внутреннего цикла производятся <tex> n - 1 </tex> сравнений, а так как внутренний цикл запускается также <tex> n - 1 </tex> раз, то за весь алгоритм сортировки производятся <tex> (n - 1)^2 </tex> сравнений. В оптимизированной версии точное количество сравнений зависит от исходного массива. Известно, что худший случай равен <tex dpi=150> \frac {n (n - 1)} {2} </tex>, а лучший {{---}} <tex> n-1 </tex>. Следовательно, <tex> T_1 = O(n^2) </tex>. В итоге получаем <tex> T = T_1 + T_2 = O(n^2) + O(n^2) = O(n^2) </tex>. == Пример работы алгоритма == Возьмём массив <tex> [5, 1, 4, 2, 8] </tex> и отсортируем значения по возрастанию, используя сортировку пузырьком. Выделены те элементы, которые сравниваются на данном этапе.  '''Первый проход:''' {| style="background-color:#CCC;margin:0.5px"!style="background-color:#EEE"| До!style="background-color:#EEE"| После!style="background-color:#EEE"| Описание шага|-|style="background-color:#FFF;padding:2px 10px"| '''5 1''' 4 2 8|style="background-color:#FFF;padding:2px 10px"| '''1 5''' 4 2 8|style="background-color:#FFF;padding:2px 10px"| Здесь алгоритм сравнивает два первых элемента и меняет их местами.|-|style="background-color:#FFF;padding:2px 10px"| 1 '''5 4''' 2 8 |style="background-color:#FFF;padding:2px 10px"| 1 '''4 5''' 2 8|style="background-color:#FFF;padding:2px 10px"| Меняет местами, так как 5 > 4|-|style="background-color:#FFF;padding:2px 10px"| 1 4 '''5 2''' 8|style="background-color:#FFF;padding:2px 10px"| 1 4 '''2 5'''8|style="background-color:#FFF;padding:2px 10px"| Меняет местами, так как 5 > 2|-|style="background-color:#FFF;padding:2px 10px"| 1 4 2 '''5 8''' |style="background-color:#FFF;padding:2px 10px"| 1 4 2 '''5 8'''|style="background-color:#FFF;padding:2px 10px"| Теперь, ввиду того, что элементы стоят на своих местах (8 > 5), алгоритм не меняет их местами.|} '''Второй проход:''' {| style="background-color:#CCC;margin:0.5px"!style="background-color:#EEE"| До!style="background-color:#EEE"| После!style="background-color:#EEE"| Описание шага|-|style="background-color:#FFF;padding:2px 10px"| '''1 4''' 2 5 8|style="background-color:#FFF;padding:2px 10px"| '''1 4''' 2 5 8|style="background-color:#FFF;padding:2px 10px"| |-|style="background-color:#FFF;padding:2px 10px"| 1 '''4 2''' 5 8|style="background-color:#FFF;padding:2px 10px"| 1 '''2 4''' 5 8|style="background-color:#FFF;padding:2px 10px"| Меняет местами, так как 4 > 2|-|style="background-color:#FFF;padding:2px 10px"| 1 2 '''4 5''' 8|style="background-color:#FFF;padding:2px 10px"| 1 2 '''4 5''' 8|style="background-color:#FFF;padding:2px 10px"||-|style="background-color:#FFF;padding:2px 10px"| 1 2 4 '''5 8''' |style="background-color:#FFF;padding:2px 10px"| 1 2 4 '''5 8'''|style="background-color:#FFF;padding:2px 10px"||} Теперь массив полностью отсортирован, но неоптимизированный алгоритм проведет еще два прохода, на которых ничего не изменится, в отличие от алгоритма, использующего вторую оптимизацию, который сделает один проход и прекратит свою работу, так как не сделает за этот проход ни одного обмена. == Модификации == === Сортировка простыми обменамичет-нечет ==='''Сортировка чет-нечет''' (англ. ''odd-even sort'') {{---}} модификация пузырьковой сортировки, основанная на сравнении элементов стоящих на четных и нечетных позициях независимо друг от друга. Сложность {{---}} <tex> O(n^2) </tex>.Псевдокод указан ниже: '''function''' oddEvenSort(a): '''for''' i = 0 '''to''' 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]) '''else''' '''for''' j = 1 '''to''' n - 1 '''step''' 2 '''if''' a[j] < a[j - 1] swap(a[j - 1], a[j]) Преимущество этой сортировки {{---}} на нескольких процессорах она выполняется быстрее, так как четные и нечетные индексы сортируются параллельно. === Сортировка расческой ==='''Сортировка расческой''' (англ. ''bubble comb sort'') — простой алгоритм {{---}} модификация пузырьковой сортировки, основанной на сравнении элементов на расстоянии. Сложность алгоритма {{---}} <tex> O(n^2) </tex>, но стремится к <tex> O(n \log n) </tex>. Является самой быстрой квадратичной сортировкой. Недостаток {{---}} она неустойчива. Псевдокод указан ниже:  '''function''' combSort(a): O k = 1.3 jump = n '''bool''' swapped = ''true'' '''while''' jump > 1 '''and''' swapped '''if''' jump > 1 jump /= k swapped = ''false'' '''for''' i = 0 '''to''' size - jump - 1 '''if''' a[i + jump] < a[i] swap(a[i], a[i + jump]) swapped = ''true''Пояснения: Изначально расстояние между сравниваемыми элементами равно <tex dpi=150> \frac{n}{k} </tex>, где <tex> k = 1{.}3 </tex> {{---}} оптимальное число для этого алгоритма. Сортируем массив по этому расстоянию, потом уменьшаем его по этому же правилу. Когда расстояние между сравниваемыми элементами достигает единицы, массив досортировывается обычным пузырьком. === Сортировка перемешиванием ==='''Сортировка перемешиванием''' (англ. ''cocktail sort''), также известная как '''Шейкерная сортировка''²' {{---}} разновидность пузырьковой сортировки, сортирующая массив в двух направлениях на каждой итерации. В среднем, сортировка перемешиванием работает в два раза быстрее пузырька. Сложность {{---}} <tex> O(n^2) </tex>, но стремится она к <tex> O(k \cdot n)</tex>, где <tex> k </tex> {{---}} максимальное расстояние элемента в неотсортированном массиве от его позиции в отсортированном массиве.Псевдокод указан ниже:

'''function''' shakerSort(a): 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 '''break''' swapped = ''false'' end-- '''for''' i = end '''downto''' begin '''if''' a[i] > a[i + 1] swap(a[i], выполняется обмен элементовa[i + 1]) swapped = ''true'' == См. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортировантакже ==* [[Сортировка выбором]]* [[Сортировка вставками]]* [[Сортировка кучей]]* [[Сортировка слиянием]]* [[Быстрая сортировка]]* [[Сортировка подсчетом]] == Источники информации ==* [http://en.wikipedia.org/wiki/Bubble_sort Сортировка пузырьком {{---}} Википедия]* [http://rain.ifmo.ru/cat/view.php/vis/sorts/quadratic-2010 Визуализатор]* [http://en.wikipedia.org/wiki/Odd%E2%80%93even_sort Сортировка чет-нечет {{---}} Википедия]* [http://en.wikipedia.org/wiki/Comb_sort Сортировка расческой {{---}} Википедия]* [http://en.wikipedia. При проходе алгоритма, элемент, стоящий не на своём месте, «всплывает» до нужной позиции как пузырёк в воде, отсюда org/wiki/Cocktail_sort Сортировка перемешиванием {{---}} Википедия] [[Категория: Дискретная математика и название алгоритма.алгоритмы]][[Категория: Сортировка]][[Категория: Квадратичные сортировки]]