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

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

Как работает Bubble Sort?

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

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

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

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

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

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

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

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

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

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

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

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

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

Алгоритм

Мы предполагаем, что список — это массив из 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

ПСЕВДОКОД

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

Чтобы облегчить проблему, мы используем одну переменную flag 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, пожалуйста, нажмите здесь .