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

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

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

Анализ [ править ]

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

Производительность [ править ]

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

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

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

Кролики и черепахи [ править ]

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

Были предприняты различные попытки уничтожить черепах, чтобы повысить скорость сортировки пузырей. Сортировка коктейлей - это двунаправленная сортировка пузырьков, которая идет от начала до конца, а затем меняет свое направление, идя от конца к началу. Он может довольно хорошо перемещать черепах, но сохраняет сложность наихудшего случая O (n 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 ( : список из сортируемых элементов ) п : = длина ( ) повтор местами : = ложь для I : = 1 до п - 1 включительно Do / * если эта пара находится вне от порядка * / если [ я - 1 ] > A [ i ] затем / * поменять местами                                     их  и  запомнить,  что что-то  изменилось  * /  swap ( A [ i - 1 ] ,  A [ i ])  swapped  : =  true  end  if  end  for  пока  не  поменяно местами end  procedure

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

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

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

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

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

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

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

Используйте [ редактировать ]

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

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

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

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

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

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

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

Варианты [ править ]

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

Споры по поводу имени [ править ]

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

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

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

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

В популярной культуре [ править ]

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

Заметки [ править ]

  1. ^ Cortesi, Aldo (27 апреля 2007). «Визуализация алгоритмов сортировки» . Проверено 16 марта 2017 года .
  2. ^ "[JDK-6804124] (coll) Замените" модифицированная сортировка слиянием "в java.util.Arrays.sort на timsort - Система ошибок Java" . bugs.openjdk.java.net . Проверено 11 января 2020 .
  3. ^ Питерс, Тим (2002-07-20). "[Python-Dev] Сортировка" . Проверено 11 января 2020 .
  4. ^ а б Астрахан, Оуэн (2003). «Сортировка пузырей: археологический алгоритмический анализ» (PDF) . Бюллетень ACM SIGCSE . 35 (1): 1–5. DOI : 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. ↑ Black, Paul E. (24 августа 2009 г.). «пузырьковая сортировка» . Словарь алгоритмов и структур данных . Национальный институт стандартов и технологий . Проверено 1 октября 2014 года .
  8. ^ Лай Стирланд, Сара (2007-11-14). «Обама проходит интервью в Google» . Проводной . Проверено 27 октября 2020 .
  9. ↑ Барак Обама, Эрик Шмидт (14 ноября 2007 г.). Барак Обама | Кандидаты в Google (Youtube). Маунтин-Вью, CA 94043 Googleplex: переговоры с Google. Событие происходит в 23:20. Архивировано из оригинала (видео) 7 сентября 2019 года . Проверено 18 сентября 2019 года . CS1 maint: location ( ссылка )

Ссылки [ править ]

  • Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Штайн . Введение в алгоритмы , второе издание. 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 пар во время сортировки)