Cout << "Bubble Sort";
Matvey Seregin
Привет! Сегодня мы рассмотрим один из самых простых, но в то же время важных алгоритмов сортировки - сортировку пузырьком.
Название алгоритма:
Bubble Sort
Принцип работы:
Сортировка пузырьком - это одна из сортировок обменом. Это значит, что "пузырёк" попарно сравнивает элементы и сортирует (меняет) их по определённому критерию.
Идея алгоритма такова: мы рассматриваем пару элементов-соседей, и если левый элемент в паре больше правого, то мы меняем их друг с другом. Так, за один проход по массиву в его конец перемещается один максимальный элемент (из тех, что мы еще не сортировали). Ниже приведен пример реализации этого алгоритма на языке программирования С++.
Реализация:
Разбор алгоритма:
В начале мы создаем массив arr размером n элементов (заметьте, массив статический, поэтому если мы указываем его размер через переменную, то она должна быть константной, речь об этом пойдет в дальнейших статьях). Также мы создаем "временную" переменную temp, которую будем использовать для обмена значениями непосредственно в процессе сортировки.
Отсортируем массив с помощью двух циклов for: внешний будет отвечать за то, чтобы пройтись по всем элементам массива, а вложенный - непосредственно за сравнение значений. Отметим, что во вложенном цикле важно перебирать элементы до n - 1, чтобы не выйти за границы массива при получении значения arr[j + 1]. Внутри цикла будем сравнивать соседние значения друг с другом и менять их, если левый окажется больше правого (подумайте, почему необходимо использовать третью переменную).
После проделанных действий выведем массив и убедимся в том, что он отсортирован:
Поздравляю, мы реализовали собственную сортировку пузырьком! :)
Визуализация алгоритма:
https://dev-props.com/notes/sorting-algorithm/ (очень наглядная визуализация, найдите сортировку пузырьком и нажмите "sort")
https://www.youtube.com/watch?v=lyZQPjUT5B4 (интересный и необычный вариант визуализации в виде танца)
Стоит отметить, что этот алгоритм используется исключительно в учебных целях, потому что он медленный и неэффективный относительно других. Однако он прост для понимания, и на этапе изучения алгоритмов очень важно осознать принцип его работы, чтобы в будущем можно было реализовывать что-то более сложное.
Не бойтесь трудностей в процессе обучения, это абсолютно нормально. Если у вас есть какие-то вопросы по статье или предложения по улучшению ее качества, мы всегда рады обратной связи.
С ув. ваш TechMentor.