1632
правки
Изменения
м
== Псевдокод ==Ниже приведен псевдокод сортировки пузырьком, на вход которой подается массив <tex> A </tex>, состоящий из <tex> a[0..n - 1] </tex> элементов. BubbleSort '''function''' bubbleSort(Aa): '''for ''' i = 0 '''to ''' n - 2 '''for ''' j = 0 '''to ''' n - 2 '''if A''' a[j] > Aa[j + 1] swap(Aa[j], Aa[j + 1]);
Тогда При использовании первой оптимизации сортировка примет такой принимает следующий вид: BubbleSort '''function''' bubbleSort(Aa): '''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 == true t = ''false;'' '''for ''' j = 0 '''to ''' n - i - 2 '''if A''' a[j] > Aa[j + 1] swap(Aa[j], Aa[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>.
rollbackEdits.php mass rollback
'''Сортировка простыми обменами''', '''сортиро́вка пузырько́мсортировка пузырьком''' (англ. ''bubble sort'') — простой алгоритм один из квадратичных алгоритмов сортировки. Сложность алгоритма: <tex>O(n^2)</tex>
== Алгоритм ==
Алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы На каждой итерации последовательно сравниваются попарно соседние элементы, и, если порядок в паре неверный, выполняется обмен элементовто элементы меняют местами. Проходы За каждый проход по массиву повторяются до тех поркак минимум один элемент встает на свое место, пока на очередном проходе поэтому необходимо совершить не окажетсяболее <tex> n - 1 </tex> проходов, что обмены больше не нужныгде <tex> n </tex> размер массива, что означает — чтобы отсортировать массив отсортирован. При проходе алгоритма, элемент, стоящий не на своём месте, «всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма.
== Оптимизация ==
* Также заметим, что если после выполнения внутреннего цикла не произошло ни одного обмена, то массив уже отсортирован, и продолжать что-то делать бессмысленно. Поэтому внутренний цикл можно выполнять не <tex> n - 1 </tex> раз, а до тех пор, пока во внутреннем цикле происходят обмены.
== Пример работы алгоритма ==
Возьмём массив с числами «5 <tex> [5, 1 , 4 , 2 8» , 8] </tex> и отсортируем значения по возрастанию, используя сортировку пузырьком. Выделены те элементы, которые сравниваются на данном этапе.
|}
Теперь массив полностью отсортирован, но неоптимизированный алгоритм проведет еще 2 два прохода, на которых ничего не изменится, в отличие от алгоритма, использующего вторую оптимизацию, который сделает один проход и прекратит свою работу, так как не сделает за этот проход ни одного обмена. == Модификации == === Сортировка чет-нечет ==='''Сортировка чет-нечет''' (англ. ''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://ruen.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 Сортировка перемешиванием {{---}} Википедия]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: СортировкиСортировка]][[Категория: Квадратичные сортировки]]
