Сортировка пузырьком — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Пример работы алгоритма)
м (rollbackEdits.php mass rollback)
 
(не показано 148 промежуточных версий 10 участников)
Строка 1: Строка 1:
'''Алгоритм сортировки''' — это алгоритм для упорядочивания элементов. Поле, служащее критерием порядка, называется ключом сортировки. На практике в качестве ключа часто выступает число, а в остальных полях хранятся какие-либо данные, никак не влияющие на работу алгоритма.
+
'''Сортировка простыми обменами''', '''сортировка пузырьком''' (англ. ''bubble sort'') — один из квадратичных алгоритмов сортировки.
 
 
'''Сортировка простыми обменами''', '''сортиро́вка пузырько́м''' (англ. ''bubble sort'') — простой алгоритм сортировки. Сложность алгоритма: O(''n''²).
 
  
 
== Алгоритм ==
 
== Алгоритм ==
Алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При проходе алгоритма, элемент, стоящий не на своём месте, «всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма.
+
Алгоритм состоит в повторяющихся проходах по сортируемому массиву. На каждой итерации последовательно сравниваются соседние элементы, и, если порядок в паре неверный, то элементы меняют местами. За каждый проход по массиву как минимум один элемент встает на свое место, поэтому необходимо совершить не более <tex> n - 1 </tex> проходов, где <tex> n </tex> размер массива, чтобы отсортировать массив.
  
== Псевдокод ==
+
Ниже приведен псевдокод сортировки пузырьком, на вход которой подается массив <tex> a[0..n - 1] </tex>.
'''Вход:''' массив A, состоящий из элементов A[0], A[1], ..., A[n-1], который требуется отсортировать по возрастанию
+
  '''function''' bubbleSort(a):
   
+
   '''for''' i = 0 '''to''' n - 2
   '''цикл для''' i = 0, 1, ..., n − 1:
+
     '''for''' j = 0 '''to''' n - 2
     '''цикл для''' j = i + 1, ..., n 2:
+
       '''if''' a[j] > a[j + 1]
       '''если''' A[j] > A[j+1], '''то''':
+
         swap(a[j], a[j + 1])
         обменять местами элементы A[j] и A[j+1]
 
  
 
== Оптимизация ==
 
== Оптимизация ==
* Внутренний цикл можно выполнять для <tex>j = 0, 1, ..., n - i - 1</tex>, где <tex>i</tex> — номер итерации внешнего цикла, так как на <tex>i</tex>-й итерации последние <tex>i</tex> элементов массива уже будут правильно упорядочены.
+
* Можно заметить, что после <tex> i </tex>-ой итерации внешнего цикла <tex> i </tex> последних элементов уже находятся на своих местах в отсортированном порядке, поэтому нет необходимости производить их сравнения друг с другом. Следовательно, внутренний цикл можно выполнять не до <tex> n - 2 </tex>, а до <tex> n - i - 2 </tex>.
* Внешний цикл можно заменить на цикл вида: пока произведится хотя бы один обмен на очередной итерации внешнего цикла, продолжать выполнение.
+
* Также заметим, что если после выполнения внутреннего цикла не произошло ни одного обмена, то массив уже отсортирован, и продолжать что-то делать бессмысленно. Поэтому внутренний цикл можно выполнять не <tex> n - 1 </tex> раз, а до тех пор, пока во внутреннем цикле происходят обмены.
И тогда псевдокод будет выглядеть так:
+
 
t := истина
+
При использовании первой оптимизации сортировка принимает следующий вид:
  '''цикл пока''' t:
+
  '''function''' bubbleSort(a):
   t := ложь
+
   '''for''' i = 0 '''to''' n - 2
  '''цикл для''' j = 0, 1, ..., n 2:
+
    '''for''' j = 0 '''to''' n - i - 2
    '''если''' A[j] > A[j+1], '''то''':
+
      '''if''' a[j] > a[j + 1]
       обменять местами элементы A[j] и A[j+1]
+
        swap(a[j], a[j + 1])
      t := истина
+
 
 +
При использовании же обеих оптимизаций сортировка пузырьком выглядит так:
 +
'''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>.
  
 
== Пример работы алгоритма ==
 
== Пример работы алгоритма ==
  
Возьмём массив с числами «5 1 4 2 и отсортируем значения по возрастанию, используя сортировку пузырьком. Выделены те элементы, которые сравниваются на данном этапе.
+
Возьмём массив <tex> [5, 1, 4, 2, 8] </tex> и отсортируем значения по возрастанию, используя сортировку пузырьком. Выделены те элементы, которые сравниваются на данном этапе.
  
  
 
'''Первый проход:'''
 
'''Первый проход:'''
  
('''5 1''' 4 2 8) ('''1 5''' 4 2 8), Здесь алгоритм сравнивает два первых элемента и меняет их местами.
+
{| 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), алгоритм не меняет их местами.
 +
|}
  
(1 '''5 4''' 2 8) (1 '''4 5''' 2 8), Меняет местами, так как 5 > 4
+
'''Второй проход:'''
  
(1 4 '''5 2''' 8) (1 4 '''2 5''' 8), Меняет местами, так как 5 > 2
+
{| 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"|
 +
|}
  
(1 4 2 '''5 8''') (1 4 2 '''5 8'''), Теперь, ввиду того, что элементы стоят на своих местах (8 > 5), алгоритм не меняет их местами.
+
Теперь массив полностью отсортирован, но неоптимизированный алгоритм проведет еще два прохода, на которых ничего не изменится, в отличие от алгоритма, использующего вторую оптимизацию, который сделает один проход и прекратит свою работу, так как не сделает за этот проход ни одного обмена.
  
 +
== Модификации ==
  
'''Второй проход:'''
+
=== Сортировка чет-нечет ===
 +
'''Сортировка чет-нечет''' (англ. ''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])
  
('''1 4''' 2 5 8) ('''1 4''' 2 5 8)
+
Преимущество этой сортировки {{---}} на нескольких процессорах она выполняется быстрее, так как четные и нечетные индексы сортируются параллельно.
  
(1 '''4 2''' 5 8) (1 '''2 4''' 5 8), Меняет местами, так как 4 > 2
+
=== Сортировка расческой ===
 +
'''Сортировка расческой''' (англ. ''comb sort'') {{---}} модификация пузырьковой сортировки, основанной на сравнении элементов на расстоянии.  Сложность  {{---}} <tex> O(n^2) </tex>, но стремится к <tex>         O(n \log n) </tex>.  Является самой быстрой квадратичной сортировкой. Недостаток {{---}} она неустойчива. Псевдокод указан ниже:
  
(1 2 '''4 5''' 8) (1 2 '''4 5''' 8)
+
'''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> {{---}} оптимальное число для этого алгоритма. Сортируем массив по этому расстоянию, потом уменьшаем его по этому же правилу. Когда  расстояние между сравниваемыми элементами достигает единицы, массив досортировывается обычным пузырьком.
  
(1 2 4 '''5 8''') (1 2 4 '''5 8''')
+
=== Сортировка перемешиванием  ===
 +
'''Сортировка перемешиванием''' (англ. ''cocktail sort''), также известная как '''Шейкерная сортировка'''   {{---}} разновидность пузырьковой сортировки, сортирующая массив в двух направлениях на каждой итерации. В среднем, сортировка перемешиванием работает в два раза быстрее пузырька. Сложность  {{---}} <tex> O(n^2) </tex>, но стремится она к <tex> O(k \cdot n) </tex>, где <tex> k </tex> {{---}} максимальное расстояние элемента в неотсортированном массиве от его позиции в отсортированном массиве. Псевдокод указан ниже:
  
Теперь массив полностью отсортирован, но неоптимизированный алгоритм проведет еще 2 прохода, на которых ничего не изменится.
+
'''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''
  
 
== См. также ==
 
== См. также ==
Строка 62: Строка 165:
 
* [[Сортировка подсчетом]]
 
* [[Сортировка подсчетом]]
  
== Источники ==
+
== Источники информации ==
* [http://ru.wikipedia.org/wiki/Сортировка_пузырьком Википедия - свободная энциклопедия]
+
* [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 Сортировка перемешиванием {{---}} Википедия]
 +
 
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Сортировка]]
 +
[[Категория: Квадратичные сортировки]]

Текущая версия на 19:41, 4 сентября 2022

Сортировка простыми обменами, сортировка пузырьком (англ. bubble sort) — один из квадратичных алгоритмов сортировки.

Алгоритм

Алгоритм состоит в повторяющихся проходах по сортируемому массиву. На каждой итерации последовательно сравниваются соседние элементы, и, если порядок в паре неверный, то элементы меняют местами. За каждый проход по массиву как минимум один элемент встает на свое место, поэтому необходимо совершить не более [math] n - 1 [/math] проходов, где [math] n [/math] размер массива, чтобы отсортировать массив.

Ниже приведен псевдокод сортировки пузырьком, на вход которой подается массив [math] a[0..n - 1] [/math].

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])

Оптимизация

  • Можно заметить, что после [math] i [/math]-ой итерации внешнего цикла [math] i [/math] последних элементов уже находятся на своих местах в отсортированном порядке, поэтому нет необходимости производить их сравнения друг с другом. Следовательно, внутренний цикл можно выполнять не до [math] n - 2 [/math], а до [math] n - i - 2 [/math].
  • Также заметим, что если после выполнения внутреннего цикла не произошло ни одного обмена, то массив уже отсортирован, и продолжать что-то делать бессмысленно. Поэтому внутренний цикл можно выполнять не [math] n - 1 [/math] раз, а до тех пор, пока во внутреннем цикле происходят обмены.

При использовании первой оптимизации сортировка принимает следующий вид:

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

Сложность

В данной сортировке выполняются всего два различных вида операции: сравнение элементов и их обмен. Поэтому время всего алгоритма [math] T = T_1 + T_2 [/math], где [math] T_1 [/math] — время, затрачиваемое на сравнение элементов, а [math] T_2 [/math] — время, за которое мы производим все необходимые обмены элементов.

Так как в алгоритме меняться местами могут только соседние элементы, то каждый обмен уменьшает количество инверсий на единицу. Следовательно, количество обменов равно количеству инверсий в исходном массиве вне зависимости от реализации сортировки. Максимальное количество инверсий содержится в массиве, элементы которого отсортированы по убыванию. Несложно посчитать, что количество инверсий в таком массиве [math] \frac {n (n - 1)} {2} [/math]. Получаем, что [math] T_2 = O(n^2) [/math].

В неоптимизированной реализации на каждой итерации внутреннего цикла производятся [math] n - 1 [/math] сравнений, а так как внутренний цикл запускается также [math] n - 1 [/math] раз, то за весь алгоритм сортировки производятся [math] (n - 1)^2 [/math] сравнений.

В оптимизированной версии точное количество сравнений зависит от исходного массива. Известно, что худший случай равен [math] \frac {n (n - 1)} {2} [/math], а лучший — [math] n-1 [/math]. Следовательно, [math] T_1 = O(n^2) [/math].

В итоге получаем [math] T = T_1 + T_2 = O(n^2) + O(n^2) = O(n^2) [/math].

Пример работы алгоритма

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


Первый проход:

До После Описание шага
5 1 4 2 8 1 5 4 2 8 Здесь алгоритм сравнивает два первых элемента и меняет их местами.
1 5 4 2 8 1 4 5 2 8 Меняет местами, так как 5 > 4
1 4 5 2 8 1 4 2 5 8 Меняет местами, так как 5 > 2
1 4 2 5 8 1 4 2 5 8 Теперь, ввиду того, что элементы стоят на своих местах (8 > 5), алгоритм не меняет их местами.

Второй проход:

До После Описание шага
1 4 2 5 8 1 4 2 5 8
1 4 2 5 8 1 2 4 5 8 Меняет местами, так как 4 > 2
1 2 4 5 8 1 2 4 5 8
1 2 4 5 8 1 2 4 5 8

Теперь массив полностью отсортирован, но неоптимизированный алгоритм проведет еще два прохода, на которых ничего не изменится, в отличие от алгоритма, использующего вторую оптимизацию, который сделает один проход и прекратит свою работу, так как не сделает за этот проход ни одного обмена.

Модификации

Сортировка чет-нечет

Сортировка чет-нечет (англ. odd-even sort) — модификация пузырьковой сортировки, основанная на сравнении элементов стоящих на четных и нечетных позициях независимо друг от друга. Сложность — [math] O(n^2) [/math]. Псевдокод указан ниже:

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) — модификация пузырьковой сортировки, основанной на сравнении элементов на расстоянии. Сложность — [math] O(n^2) [/math], но стремится к [math] O(n \log n) [/math]. Является самой быстрой квадратичной сортировкой. Недостаток — она неустойчива. Псевдокод указан ниже:

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

Пояснения: Изначально расстояние между сравниваемыми элементами равно [math] \frac{n}{k} [/math], где [math] k = 1{.}3 [/math] — оптимальное число для этого алгоритма. Сортируем массив по этому расстоянию, потом уменьшаем его по этому же правилу. Когда расстояние между сравниваемыми элементами достигает единицы, массив досортировывается обычным пузырьком.

Сортировка перемешиванием

Сортировка перемешиванием (англ. cocktail sort), также известная как Шейкерная сортировка — разновидность пузырьковой сортировки, сортирующая массив в двух направлениях на каждой итерации. В среднем, сортировка перемешиванием работает в два раза быстрее пузырька. Сложность — [math] O(n^2) [/math], но стремится она к [math] O(k \cdot n) [/math], где [math] k [/math] — максимальное расстояние элемента в неотсортированном массиве от его позиции в отсортированном массиве. Псевдокод указан ниже:

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

См. также

Источники информации