Структура данных - алгоритм пузырьковой сортировки
Сортировка пузырьков - это простой алгоритм сортировки. Этот алгоритм сортировки основан на сравнении, в котором сравнивается каждая пара смежных элементов, и элементы меняются местами, если они не в порядке. Этот алгоритм не подходит для больших наборов данных, так как его средняя и худшая сложность составляют Ο (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, нажмите здесь .