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

редактировать

Алгоритм сортировки простым сравнением

Пузырьковая сортировка
Статическая визуализация пузырьковой сортировки
Класс	Алгоритм сортировки
Структура данных	Массив
наихудший случай производительность	$O (n 2) {\ displaystyle O (n ^ {2})}$ $O (n ^ {2})$ сравнения, $O (n 2) {\ displaystyle O (n ^ {2})}$ $O (n ^ {2})$ swaps
Лучший случай производительность	$O (n) {\ displaystyle O (n)}$ $O (n)$ сравнения, $O (1) {\ displaystyle O (1)}$ $O (1)$ swaps
Средняя производительность	$O ( n 2) {\ displaystyle O (n ^ {2})}$ $O (n ^ {2})$ сравнения, $O (n 2) {\ displaystyle O (n ^ {2})}$ $O (n ^ {2})$ свопы
наихудший случай сложность пространства	$O (n) {\ displaystyle O (n)}$ $O (n)$ всего, $O (1) {\ displaystyle O (1)}$ $O (1)$ вспомогательный

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

Этот простой алгоритм плохо работает в реальном мире и используется в основном как обучающий инструмент. Более эффективные алгоритмы, такие как quicksort, timsort или merge sort, используются библиотеками сортировки, встроенными в популярные языки программирования, такие как Python и Java.

Содержание

1 Анализ
- 1.1 Производительность
- 1.2 Кролики и черепахи
- 1.3 Пошаговый пример
2 Реализация
- 2.1 Реализация псевдокода
- 2.2 Оптимизация пузырьковой сортировки
3 Используйте
4 Вариации
5 Споры по поводу имени
6 В популярной культуре
7 Примечания
8 Ссылки
9 Внешние ссылки

Анализ

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

Производительность

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

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

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

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

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

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

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

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

Первый проход: ( 514 2 8) → (154 2 8). Здесь алгоритм сравнивает первые два элемента и меняет местами, начиная с 5>1.; (1 542 8) → (1 452 8), поменять местами с 5>4; (1 4 528) → (1 4 258), поменять местами с 5>2; (1 4 2 58) → (1 4 2 58). Теперь, поскольку эти элементы уже упорядочены (8>5), алгоритм не меняет их местами.
Второй проход: ( 142 5 8) → (142 5 8); (1 425 8) → (1 245 8), поменять местами с 4>2; (1 2 458) → (1 2 458); (1 2 4 58) → (1 2 4 58)

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

Третий проход: ( 124 5 8) → (124 5 8); (1 245 8) → (1 245 8); (1 2 458) → (1 2 458); (1 2 4 58) → (1 2 4 58)

Реализация

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

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

процедура bubbleSort (A: список сортируемых элементов) n: = length (A) repeat swapped: = false для i: = от 1 до n-1 включительно do / * если эта пара не в порядке * / если A [i-1]>A [i], то / * поменять местами их и запомнить что-то измененное * / swap (A [i-1], A [i]) swapped: = true end if end for пока не будет заменен конец процедуры

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

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

процедура bubbleSort (A: список сортируемых элементов) n: = length (A) repeat swapped: = false for i: = от 1 до n - 1 включительно do, если A [i - 1]>A [i], затем поменять местами (A [i - 1], A [i]) swapped = true end if end for n: = n - 1 пока не поменяется местами конец процедуры

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

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

процедура bubbleSort (A: список сортируемых элементов) n: = length (A) repeat newn: = 0 for i: = от 1 до n - 1 включительно do if A [i - 1]>A [i], затем поменять местами (A [i - 1], A [i]) newn: = i end if end для n: = newn до n ≤ 1 процедура завершения

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

Используйте

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

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

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

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

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

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

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

Варианты

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

Споры по поводу названия

Сортировка пузырьков иногда упоминается как «тонущая сортировка».

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

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

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

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

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

Примечания

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

Ссылки

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

Внешние ссылки

Викибук Реализация алгоритма имеет страницу по теме: Пузырьковая сортировка

Викискладе есть материалы, связанные с пузырьковой сортировкой.

В Викиверситете есть учебные ресурсы по пузырьковой сортировке

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