WikiDer > Пузырьковая сортировка

Bubble sort
Пузырьковая сортировка
Bubblesort-edited-color.svg
Статическая визуализация пузырьковой сортировки[1]
Учебный классАлгоритм сортировки
Структура данныхМножество
Худший случай спектакль сравнения, свопы
Лучший случай спектакль сравнения, свопы
Средний спектакль сравнения, свопы
Худший случай космическая сложность общий, вспомогательный

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

Этот простой алгоритм плохо работает в реальном мире и используется в основном как обучающий инструмент. Более эффективные алгоритмы, такие как быстрая сортировка, Timsort, или же Сортировка слиянием используются библиотеками сортировки, встроенными в популярные языки программирования, такие как Python и Java.[2][3]

Анализ

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

Спектакль

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

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

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

Кролики и черепахи

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

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

Пошаговый пример

Возьмите массив чисел «5 1 4 2 8» и отсортируйте его от наименьшего числа к наибольшему, используя пузырьковую сортировку. На каждом этапе элементы, написанные на смелый сравниваются. Потребуется три прохода;

Первый проход
( 5 1 4 2 8 ) → ( 1 5 4 2 8). Здесь алгоритм сравнивает первые два элемента и меняет местами, поскольку 5> 1.
( 1 5 4 2 8 ) → ( 1 4 5 2 8), поменять местами, поскольку 5> 4
( 1 4 5 2 8 ) → ( 1 4 2 5 8), поменять местами, поскольку 5> 2
( 1 4 2 5 8 ) → ( 1 4 2 5 8 ), Теперь, поскольку эти элементы уже в порядке (8> 5), алгоритм не меняет их местами.
Второй проход
( 1 4 2 5 8 ) → ( 1 4 2 5 8 )
( 1 4 2 5 8 ) → ( 1 2 4 5 8), поменять местами, поскольку 4> 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 )
( 1 2 4 5 8 ) → ( 1 2 4 5 8 )

Выполнение

Реализация псевдокода

В псевдокод алгоритм может быть выражен как (массив на основе 0):

процедура bubbleSort(А : список из сортируемый Предметы)    п := длина(А)    повторение        поменяны местами := ложный        за я := 1 к п-1 включающий делать            /* если это пара является из из порядок */            если А[я-1] > А[я] тогда                /* замена их и Помните что нибудь измененный */                замена(А[я-1], А[я])                поменяны местами := истинный            конец если        конец за    до того как нет поменяны местамиконец процедура

Оптимизация пузырьковой сортировки

Алгоритм пузырьковой сортировки можно оптимизировать, заметив, что п-й проход находит п-й по величине элемент и ставит его на последнее место. Таким образом, внутренний цикл может не смотреть на последний п - 1 шт. При беге за п-й раз:

процедура bubbleSort(А : список из сортируемый Предметы)    п := длина(А)    повторение        поменяны местами := ложный        за я := 1 к п - 1 включающий делать            если А[я - 1] > А[я] тогда                замена(А[я - 1], А[я])                поменяны местами = истинный            конец если        конец за        п := п - 1    до того как нет поменяны местамиконец процедура

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

Для этого в псевдокоде можно записать следующее:

процедура bubbleSort(А : список из сортируемый Предметы)    п := длина(А)    повторение        новинка := 0        за я := 1 к п - 1 включающий делать            если А[я - 1] > А[я] тогда                замена(А[я - 1], А[я])                newn := я            конец если        конец за        п := newn    до того как п ≥ 1конец процедура

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

Использовать

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

Хотя пузырьковая сортировка является одним из самых простых алгоритмов сортировки для понимания и реализации, ее О(п2) сложность означает, что его эффективность резко снижается для списков, состоящих из более чем небольшого числа элементов. Даже среди простых О(п2) алгоритмы сортировки, такие алгоритмы, как вставка сортировки обычно значительно более эффективны.

Из-за своей простоты пузырьковая сортировка часто используется для ознакомления с концепцией алгоритма или алгоритма сортировки. Информатика студенты. Однако некоторые исследователи, такие как Оуэн Астрахан приложили все усилия, чтобы осудить пузырьковую сортировку и ее неизменную популярность в образовании по информатике, рекомендуя даже не преподавать ее.[4]

В Файл жаргона, который классно называет Богосорт «архетипичный [sic] извращенно ужасный алгоритм» также называет пузырьковую сортировку «общим плохим алгоритмом».[5] Дональд Кнут, в Искусство программирования, пришел к выводу, что «пузырьковой сортировке, похоже, нечего рекомендовать, кроме запоминающегося названия и того факта, что это приводит к некоторым интересным теоретическим проблемам», некоторые из которых он затем обсуждает.[6]

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

Пузырьковая сортировка также плохо взаимодействует с современным оборудованием ЦП. Он производит как минимум вдвое больше записей, чем сортировка вставкой, в два раза больше промахов в кеш и асимптотически больше. неверные предсказания ветвей.[нужна цитата] Эксперименты Астрахана по сортировке строк в Ява показывать пузырьковую сортировку примерно на одну пятую быстрее, чем сортировка вставкой, и на 70% быстрее, чем сортировка выбора.[4]

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

Вариации

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

Споры по поводу имени

Сортировку пузырьков иногда называют «тонущей сортировкой».[7]

Например, в книге Дональда Кнута Искусство программирования, Том 3: Сортировка и поиск он заявляет в разделе 5.2.1 «Сортировка вставкой», что [значение] «устанавливается на свой надлежащий уровень» и что этот метод сортировки иногда называют просеивание или же тонущий техника.[требуется разъяснение]

Эти дебаты увековечиваются из-за легкости, с которой можно рассматривать этот алгоритм с двух разных, но одинаково обоснованных точек зрения:

  1. В больше ценности можно рассматривать как тяжелее и поэтому прогрессивно раковина к Нижний списка
  2. В меньше ценности можно рассматривать как более легкий и поэтому прогрессивно пузыриться к верх списка.

В популярной культуре

Бывший генеральный директор Google Эрик Шмидт спросил тогдашний кандидат в президенты Барак Обама однажды во время интервью о том, как лучше всего отсортировать миллион целые числа - и Обама, сделав паузу на мгновение, ответил: «Я думаю, что сортировка пузырей - неправильный путь». [8][9]

Примечания

  1. ^ Кортеси, Альдо (27 апреля 2007 г.). «Визуализация алгоритмов сортировки». Получено 16 марта 2017.
  2. ^ "[JDK-6804124] (coll) Заменить" измененную сортировку слиянием "в java.util.Arrays.sort на timsort - Система ошибок Java". bugs.openjdk.java.net. Получено 2020-01-11.
  3. ^ Питерс, Тим (2002-07-20). "[Python-Dev] Сортировка". Получено 2020-01-11.
  4. ^ а б Астрахан, Оуэн (2003). «Сортировка пузырьков: археологический алгоритмический анализ» (PDF). Бюллетень ACM SIGCSE. 35 (1): 1–5. Дои:10.1145/792548.611918. ISSN 0097-8418.
  5. ^ "жаргон, узел: bogo-sort".
  6. ^ Дональд Кнут. Искусство программирования, Том 3: Сортировка и поиск, Второе издание. Аддисон-Уэсли, 1998. ISBN 0-201-89685-0. Страницы 106–110 раздела 5.2.2: Сортировка по обмену. «[A] Хотя методы, использованные в расчетах [для анализа пузырьковой сортировки], поучительны, результаты неутешительны, поскольку они говорят нам, что пузырьковая сортировка на самом деле совсем не очень хороша. По сравнению с прямой вставкой […], пузырьковая сортировка требует более сложной программы и занимает примерно вдвое больше времени! " (Цитата из первого издания 1973 г.)
  7. ^ Блэк, Пол Э. (24 августа 2009 г.). "пузырьковая сортировка". Словарь алгоритмов и структур данных. Национальный институт стандартов и технологий. Получено 1 октября 2014.
  8. ^ Лай Стирланд, Сара (14 ноября 2007 г.). "Обама дает интервью в Google". Проводной. Получено 2020-10-27.
  9. ^ Барак Обама, Эрик Шмидт (14 ноября 2007 г.). Барак Обама | Кандидаты в Google (YouTube). Mountain View, CA 94043 Googleplex: переговоры с Google. Событие происходит в 23:20. Архивировано из оригинал (Видео) 7 сентября 2019 г.. Получено 18 сен, 2019.CS1 maint: location (связь)

Рекомендации

внешняя ссылка