Изменения

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

Алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы На каждой итерации последовательно сравниваются попарно соседние элементы, и, если порядок в паре неверный, выполняется обмен элементовто элементы меняют местами. Проходы За каждый проход по массиву повторяются до тех поркак минимум один элемент встает на свое место, пока на очередном проходе поэтому необходимо совершить не окажетсяболее <tex> n - 1 </tex> проходов, что обмены больше не нужныгде <tex> n </tex> размер массива, что означает — чтобы отсортировать массив отсортирован. При проходе алгоритма, элемент, стоящий не на своём месте, «всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма.

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

* Внутренний цикл можно выполнять для Можно заметить, что после <tex>j = 0, 1, ..., n - i - 1</tex>, где -ой итерации внешнего цикла <tex>i</tex> — номер итерации внешнего циклапоследних элементов уже находятся на своих местах в отсортированном порядке, поэтому нет необходимости производить их сравнения друг с другом. Следовательно, так как на внутренний цикл можно выполнять не до <tex>in - 2 </tex>-й итерации последние , а до <tex>n - i- 2 </tex> элементов массива уже будут правильно упорядочены.* Внешний цикл можно заменить на цикл вида: пока произведится хотя бы один обмен на очередной итерации внешнего Также заметим, что если после выполнения внутреннего циклане произошло ни одного обмена, то массив уже отсортирован, и продолжать выполнениечто-то делать бессмысленно.И тогда псевдокод будет выглядеть так: t := истина '''Поэтому внутренний цикл пока''' t: t := ложь '''цикл для''' j = 0можно выполнять не <tex> n - 1 </tex> раз, 1а до тех пор, пока во внутреннем цикле происходят обмены..., n − 2: '''если''' A[j] > A[j+1], '''то''': обменять местами элементы A[j] и A[j+1] t := истина

При использовании первой оптимизации сортировка принимает следующий вид: '''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>.

Возьмём массив с числами «5 В неоптимизированной реализации на каждой итерации внутреннего цикла производятся <tex> n - 1 4 2 8» и отсортируем значения по возрастанию</tex> сравнений, используя сортировку пузырьком. Выделены те элементыа так как внутренний цикл запускается также <tex> n - 1 </tex> раз, которые сравниваются на данном этапето за весь алгоритм сортировки производятся <tex> (n - 1)^2 </tex> сравнений.

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

(1 4 2 '''5 8Первый проход:''') (1 4 2 '''5 8'''), Теперь, ввиду того, что элементы стоят на своих местах (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 2''' 4 5 8) (and''' swapped '''if''' jump > 1 jump /= k swapped = ''false'' '''for''' i = 0 '''to'''size - jump - 1 2 ''' 4 5 8if''' 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> {{---}} оптимальное число для этого алгоритма. Сортируем массив по этому расстоянию, потом уменьшаем его по этому же правилу. Когда расстояние между сравниваемыми элементами достигает единицы, массив досортировывается обычным пузырьком.

(1 === Сортировка перемешиванием ==='''Сортировка перемешиванием'''(англ. '2 4'cocktail sort'' 5 8) (1 , также известная как '''2 4Шейкерная сортировка''' 5 8 {{---}} разновидность пузырьковой сортировки, сортирующая массив в двух направлениях на каждой итерации. В среднем, сортировка перемешиванием работает в два раза быстрее пузырька. Сложность {{---}} <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 ''4 5'if'' 8) ' a[i] > a[i + 1] swap(a[i], a[i + 1 2 ]) swapped = ''true'' '''if''' !swapped '''break''' swapped = ''false'' end-- '''for''' i = end '''downto''' begin '''4 5if''' 8a[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 Сортировка перемешиванием {{---}} Википедия]

== Ссылки ==[[Категория: Дискретная математика и алгоритмы]][[Категория: Сортировка]]* [http[Категория://ru.wikipedia.org/wiki/Сортировка_пузырьком Википедия - свободная энциклопедияКвадратичные сортировки]]