Изменения

Перейти к: навигация, поиск

Сортировка пузырьком

216 байт убрано, 00:09, 23 января 2017
объединены разделы "Алгоритм" и "Псевдокод"; отступы, пробелы после тире, равно и т.п., исправление орфографических ошибок
Алгоритм состоит в повторяющихся проходах по сортируемому массиву. На каждой итерации последовательно сравниваются соседние элементы, и, если порядок в паре неверный, то элементы меняют местами. За каждый проход по массиву как минимум один элемент встает на свое место, поэтому необходимо совершить не более <tex> n - 1 </tex> проходов, где <tex> n </tex> размер массива, чтобы отсортировать массив.
== Псевдокод ==
Ниже приведен псевдокод сортировки пузырьком, на вход которой подается массив <tex> a[0..n - 1] </tex>.
'''function''' bubbleSort(a):
При использовании первой оптимизации сортировка принимает следующий вид:
'''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
== Сложность ==
|}
Теперь массив полностью отсортирован, но неоптимизированный алгоритм проведет еще два прохода, на которых ничего не изменится, в отличии отличие от алгоритма, использующего вторую оптимизацию, который сделает один проход и прекратит свою работу, так как не сделает за этот проход ни одного обмена.
== Модификации ==
'''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> 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 = false '''break''' swapped = ''false'' end-- '''for''' i = end '''downto''' begin '''if''' a[i] > a[i + 1] swap(a[i], a[i + 1]) swapped = ''true''
== См. также ==
243
правки

Навигация