Пузырьковая сортировка - Bubble sort

Эта статья нужны дополнительные цитаты для проверка. Пожалуйста помоги улучшить эту статью к добавление цитат в надежные источники. Материал, не полученный от источника, может быть оспорен и удален Найдите источники: "Пузырьковая сортировка"  – Новости  · газеты  · книги  · ученый  · JSTOR (Ноябрь 2016) (Узнайте, как и когда удалить этот шаблон сообщения)

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

Статическая визуализация пузырьковой сортировки[1]
Учебный класс	Алгоритм сортировки
Структура данных	Множество
Худший случай спектакль	${ Displaystyle О (п ^ {2})}$ сравнения, ${ Displaystyle О (п ^ {2})}$ свопы
Лучший случай спектакль	${ Displaystyle О (п)}$ сравнения, ${ displaystyle O (1)}$ свопы
Средний спектакль	${ Displaystyle О (п ^ {2})}$ сравнения, ${ Displaystyle О (п ^ {2})}$ свопы
Худший случай космическая сложность	${ displaystyle O (1)}$ общий, ${ displaystyle O (1)}$ вспомогательный

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

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

Анализ

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

Спектакль

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

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

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

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

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

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

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

Возьмите массив чисел «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конец процедура

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

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

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

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

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

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

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

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

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

Вариации

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

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

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

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

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

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

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

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

Примечания

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

• Томас Х. Кормен, Чарльз Э. Лейзерсон, Рональд Л. Ривест, и Клиффорд Штайн. Введение в алгоритмы, Второе издание. MIT Press и McGraw-Hill, 2001. ISBN  0-262-03293-7. Задача 2-2, стр.40.
• Сортировка при наличии предсказания переходов и кешей
• Основы структур данных Эллиса Горовица, Сартадж Сахни и Сьюзен Андерсон-Фрид ISBN  81-7371-605-6
• Оуэн Астрахан. Пузырьковая сортировка: археологический алгоритмический анализ

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

• Мартин, Дэвид Р. (2007). «Анимированные алгоритмы сортировки: пузырьковая сортировка». Архивировано из оригинал на 2015-03-03. - графическая демонстрация
• "Пузырьковая сортировка Лафора". (Анимация Java-апплета)
• OEIS последовательность A008302 (таблица (статистика) количества перестановок [n], которые требуют k пар перестановок во время сортировки)