Структура данных - алгоритм пузырьковой сортировки

Сортировка пузырьков - это простой алгоритм сортировки. Этот алгоритм сортировки основан на сравнении, в котором сравнивается каждая пара смежных элементов, и элементы меняются местами, если они не в порядке. Этот алгоритм не подходит для больших наборов данных, так как его средняя и худшая сложность составляют Ο (n 2 ), гдеn количество элементов.

Как работает пузырьковая сортировка?

В качестве примера возьмем несортированный массив. Сортировка пузырьков занимает Ο (n 2 ) времени, поэтому мы делаем ее короткой и точной.

Сортировка пузырьков начинается с самых первых двух элементов, сравнивая их, чтобы проверить, какой из них больше.

В этом случае значение 33 больше 14, поэтому оно уже находится в отсортированных местах. Далее мы сравниваем 33 с 27.

Мы обнаруживаем, что 27 меньше 33, и эти два значения необходимо поменять местами.

Новый массив должен выглядеть так -

Затем мы сравниваем 33 и 35. Мы обнаруживаем, что оба находятся в уже отсортированных позициях.

Затем мы переходим к следующим двум значениям: 35 и 10.

Тогда мы знаем, что 10 меньше 35. Следовательно, они не сортируются.

Мы меняем эти значения местами. Мы обнаруживаем, что достигли конца массива. После одной итерации массив должен выглядеть так:

Чтобы быть точным, сейчас мы показываем, как должен выглядеть массив после каждой итерации. После второй итерации это должно выглядеть так -

Обратите внимание, что после каждой итерации в конце перемещается по крайней мере одно значение.

А когда свопинг не требуется, пузырьковая сортировка узнает, что массив полностью отсортирован.

Теперь мы должны рассмотреть некоторые практические аспекты пузырьковой сортировки.

Алгоритм

Мы предполагаем list это массив nэлементы. Далее предполагаем, чтоswap функция меняет местами значения заданных элементов массива.

begin BubbleSort(list)

   for all elements of list
      if list[i] > list[i+1]
         swap(list[i], list[i+1])
      end if
   end for
   
   return list
   
end BubbleSort

Псевдокод

Мы наблюдаем в алгоритме, что пузырьковая сортировка сравнивает каждую пару элементов массива, если весь массив не отсортирован полностью в порядке возрастания. Это может вызвать несколько проблем со сложностью, например, что, если массив больше не нуждается в подкачке, поскольку все элементы уже восходят.

Чтобы облегчить проблему, мы используем одну флаговую переменную swappedчто поможет нам увидеть, произошел ли какой-либо обмен или нет. Если свопинг не произошел, т. Е. Массив не требует дополнительной обработки для сортировки, он выйдет из цикла.

Псевдокод алгоритма BubbleSort можно записать следующим образом:

procedure bubbleSort( list : array of items )

   loop = list.count;
   
   for i = 0 to loop-1 do:
      swapped = false
		
      for j = 0 to loop-1 do:
      
         /* compare the adjacent elements */   
         if list[j] > list[j+1] then
            /* swap them */
            swap( list[j], list[j+1] )		 
            swapped = true
         end if
         
      end for
      
      /*if no number was swapped that means 
      array is sorted now, break the loop.*/
      
      if(not swapped) then
         break
      end if
      
   end for
   
end procedure return list

Реализация

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

Чтобы узнать о реализации пузырьковой сортировки на языке программирования C, нажмите здесь .