Изменения

'''Алгоритм сортировкиСортировка простыми обменами''', '''сортировка пузырьком''' — это алгоритм для упорядочивания элементов(англ. Поле, служащее критерием порядка, называется ключом ''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'bubble sort''a[j] > a[j + 1] swap(a[j], a[j + 1]) — простой алгоритм сортировки. Сложность алгоритма При использовании же обеих оптимизаций сортировка пузырьком выглядит так: O '''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]) Преимущество этой сортировки {{---}} на нескольких процессорах она выполняется обмен быстрее, так как четные и нечетные индексы сортируются параллельно. === Сортировка расческой ==='''Сортировка расческой''' (англ. ''comb sort'') {{---}} модификация пузырьковой сортировки, основанной на сравнении элементовна расстоянии. Сложность {{---}} <tex> O(n^2) </tex>, но стремится к <tex> O(n \log n) </tex>. Является самой быстрой квадратичной сортировкой. Недостаток {{---}} она неустойчива. Псевдокод указан ниже:  '''function''' combSort(a): 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 Сортировка перемешиванием {{---}} Википедия]

== Пвесвдокод == '''Вход:''' массив A, состоящий из элементов A[0], A[1Категория: Дискретная математика и алгоритмы], ..., A[n-1], который требуется отсортировать по возрастанию '''цикл для''' i = 0, 1, ..., n − 1[[Категория:Сортировка]] '''цикл для''' j = i + 1, ..., n − 2: '''если''' A[j] > A[j+1], '''то'''Категория: обменять местами элементы A[jКвадратичные сортировки] и A[j+1]