Метод сортировки пузырьком кратко

Обновлено: 04.07.2024

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

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

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

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

Пусть имеется список [6, 12, 4, 3, 8].

За первую итерацию внешнего цикла число 12 переместится в конец. Для этого потребуется 4 сравнения во внутреннем цикле:

6 > 12? Нет
12 > 4? Да. Меняем местами
12 > 3? Да. Меняем местами
12 > 8? Да. Меняем местами

Результат: [6, 4, 3, 8, 12]

За вторую итерацию внешнего цикла число 8 переместиться на предпоследнее место. Для этого потребуется 3 сравнения:

6 > 4? Да. Меняем местами
6 > 3? Да. Меняем местами
6 > 8? Нет

Результат: [4, 3, 6, 8, 12]

На третьей итерации внешнего цикла исключаются два последних элемента. Количество итераций внутреннего цикла равно двум:

Результат: [3, 4, 6, 8, 12]

На четвертой итерации внешнего цикла осталось сравнить только первые два элемента, поэтому количество итераций внутреннего равно единице:

Все отлично знают, что из класса обменных сортировок самый быстрый метод – это так называемая быстрая сортировка. О ней пишут диссертации, её посвящено немало статей на Хабре, на её основе придумывают сложные гибридные алгоритмы. Но сегодня речь пойдёт не про quick sort, а про другой обменный способ – старую добрую пузырьковую сортировку и её улучшения, модификации, мутации и разновидности.

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

Сегодня поговорим о простейших сортировках обменами.

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

Заранее предупрежу, что почти все приведённые способы весьма медленные и глубокого анализа их временной сложности не будет. Какие-то побыстрее, какие-то помедленнее, но, грубо говоря, можно сказать, что в среднем O(n 2 ). Также я не вижу резона загромождать статью реализациями на каких-либо языках программирования. Заинтересовавшиеся без малейшего труда смогут найти примеры кода на Розетте, в Википедии или где-нибудь ещё.

Но вернёмся к сортировкам обменами. Упорядочивание происходит в результате многократного последовательного перебора массива и сравнения пар элементов между собой. Если сравниваемые элементы не отсортированы друг относительно друга – то меняем их местами. Вопрос только в том, каким именно макаром массив обходить и по какому принципу выбирать пары для сравнения.

Начнём не с эталонной пузырьковой сортировки, а с алгоритма, который называется…

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

В этом случае перед нами не что иное как всем известная…

Если не только в конец задвигать максимумы, а ещё и в начало перебрасывать минимумы то у нас получается…

Шейкерная сортировка работает немного быстрее чем пузырьковая, поскольку по массиву в нужных направлениях попеременно мигрируют и максимумы и минимумы. Улучшения, как говорится, налицо.

image: виноватая черепашка

Первоначальный разрыв между сравниваемыми элементами лучше брать не абы какой, а с учётом специальной величины называемой фактором уменьшения, оптимальное значение которой равно примерно 1,247. Сначала расстояние между элементами равно размеру массива разделённого на фактор уменьшения (результат, естественно, округляется до ближайшего целого). Затем, пройдя массив с этим шагом, мы снова делим шаг на фактор уменьшения и проходим по списку вновь. Так продолжается до тех пор, пока разность индексов не достигнет единицы. В этом случае массив досортировывается обычным пузырьком.

Опытным и теоретическим путём установлено оптимальное значение фактора уменьшения:

Когда был изобретён этот метод, на него на стыке 70-х и 80-х мало кто обратил внимание. Десятилетие спустя, когда программирование перестало быть уделом учёных и инженеров IBM, а уже лавинообразно набирало массовый характер, способ переоткрыли, исследовали и популяризировали в 1991 году Стивен Лейси и Ричард Бокс.

Вот собственно и всё что я хотел Вам рассказать про пузырьковую сортировку и иже с ней.

* покращення (укр.) – улучшение
** Сортування бульбашкою (укр.) – Сортировка пузырьком
*** Сортування гребінцем (укр.) – Сортировка расчёской

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

( 5 1 4 2 8) ( 1 5 4 2 8), здесь алгоритм сравнивает два первых элемента и меняет их местами, так как (5>1).

(1 5 4 2 8) (1 4 5 2 8), меняет элементы местами, так как 4>4>(5>4)

(1 4 5 2 8) (1 4 2 5 8), меняет элементы местами, так как 2>(5>2)

(1 4 2 5 8 ) (1 4 2 5 8 ), ввиду того, что элементы стоят на своих местах (5>8>5), алгоритм не меняет их местами.

( 1 4 2 5 8) ( 1 4 2 5 8)

(1 4 2 5 8) (1 2 4 5 8), меняет элементы местами, так как (4>2)2>

(1 2 4 5 8) (1 2 4 5 8)

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

( 1 2 4 5 8) -> ( 1 2 4 5 8)
(1 2 4 5 8) -> (1 2 4 5 8)
(1 2 4 5 8) -> (1 2 4 5 8) )
(1 2 4 5 8 ) -> (1 2 4 5 8 )

Теперь массив отсортирован, и алгоритм может быть завершён.

Ниже в качестве примера приведена сортировка пузырьком С :

Сортировка пузырьком Java

Сортировка пузырьком Python

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

Пузырьковая сортировка Python 3

Метод пузырька C — результат сортировки:

Худшая и средняя сложность времени: O (n * n). Наихудший случай возникает, когда массив отсортирован по обратному адресу.

Сложность наилучшего случая: O (n). Наилучший случай возникает, когда массив уже отсортирован.

Пограничные случаи: сортировка занимает минимальное время (порядок n), когда элементы уже отсортированы.

Сортировка на месте: Да.

В компьютерной графике пузырьковая сортировка популярна благодаря возможности обнаруживать мелкие ошибки ( например, обмен всего двух элементов ) в почти отсортированных массивах и исправлять ее только с линейной сложностью ( 2n ). Например, она используется в алгоритме заполнения полигонов, где ограничивающие линии сортируются по их координате x на определенной линии сканирования ( линия, параллельная оси X ), и с увеличением Y их порядок меняется ( два элемента меняются местами ) только на пересечениях двух линий.

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

Пожалуйста, оставьте свои комментарии по текущей теме статьи. За комментарии, лайки, дизлайки, отклики, подписки огромное вам спасибо!

Пожалуйста, опубликуйте ваши мнения по текущей теме статьи. За комментарии, лайки, подписки, дизлайки, отклики низкий вам поклон!

Пожалуйста, оставьте свои мнения по текущей теме статьи. Мы крайне благодарны вам за ваши комментарии, дизлайки, лайки, отклики, подписки!

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

Решение

Существует множество методов сортировки. Одни из них являются более эффективными, другие – проще для понимания. Достаточно простой для понимания является сортировкаметодом пузырька, который также называют методом простого обмена. В чем же он заключается, и почему у него такое странное название: "метод пузырька"?

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

Читайте также: