Описание тега bubble-sort
Пузырьковая сортировка - это простой алгоритм сортировки, который работает, многократно проходя по списку для сортировки, сравнивая каждую пару соседних элементов и меняя их местами, если они находятся в неправильном порядке.
После первого прохода по списку самый большой элемент гарантированно окажется в конце массива (в нужном месте), а это значит, что на втором проходе нет необходимости сравнивать его. Отсутствие сравнения последних n элементов после n проходов делает сортировку пузырьков немного быстрее.
Прохождение по списку повторяется до тех пор, пока не перестанут использоваться свопы, что указывает на то, что список отсортирован. Алгоритм получил свое название от того, как более мелкие элементы "всплывают" вверх в списке. Поскольку он использует только сравнения для работы с элементами, это сортировка сравнения.
Хотя алгоритм прост, большинство других алгоритмов сортировки более эффективны для больших списков.
Пузырьковая сортировка имеет наихудшую и среднюю сложность как О(n2), где n - количество сортируемых элементов. Существует множество алгоритмов сортировки с существенно лучшей сложностью наихудшего случая или средней сложностью O(n log n). Даже другие алгоритмы сортировки О(n2), такие как сортировка вставкой, как правило, имеют лучшую производительность, чем пузырьковая сортировка. Следовательно, пузырьковая сортировка не является практическим алгоритмом сортировки, когда n велико.
Единственное существенное преимущество пузырьковой сортировки перед большинством других реализаций, даже быстрой сортировкой, но не сортировкой вставкой, заключается в том, что способность определять, что список отсортирован, эффективно встроена в алгоритм. Производительность пузырьковой сортировки по уже отсортированному списку (в лучшем случае) составляет O(n). Напротив, большинство других алгоритмов, даже с лучшей средней сложностью, выполняют весь свой процесс сортировки на множестве и, следовательно, являются более сложными.
Однако сортировка вставкой не только имеет этот механизм, но также лучше работает со списком, который существенно отсортирован (с небольшим количеством инверсий).
В случае больших коллекций следует избегать пузырьковой сортировки. При обратном порядке сбора он не будет работать. Он мало используется в промышленности, но полезен в обучении.