Алгоритм недели: пузырьковая сортировка

Странно, что пузырьковая сортировка — самый известный алгоритм сортировки на практике, поскольку это один из худших подходов к сортировке данных. Почему пузырьковая сортировка так известна? Возможно из-за его экзотического названия или потому что это так легко осуществить. Сначала давайте посмотрим на его природу.

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

1. Каждые два соседних элемента сравниваются

Если на пути появляются более тяжелые элементы, мы должны поменять их местами.

На пути к поверхности самый легкий на данный момент предмет встречает более тяжелый элемент. Затем они меняются местами.

3. Двигайтесь вперед и меняйте местами каждый более тяжелый предмет.

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

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

4. Если есть более легкий элемент, то этот предмет начинает пузыриться на поверхность

Мы можем быть уверены, что на каждом шаге алгоритм покажет самый легкий элемент

Если самый легкий на данный момент элемент встречает другой более легкий элемент, то самый новый на данный момент самый легкий элемент начинает пузыриться наверх.

5. Наконец самый легкий элемент на своем месте

Наконец список начинает выглядеть отсортированным

В конце каждой итерации мы можем быть уверены, что самый легкий элемент находится в нужном месте — в начале списка.

Проблема состоит в том, что этот алгоритм требует огромного количества comaprison, и, как мы уже знаем, это может быть медленным.

Мы можем легко увидеть, насколько неэффективна пузырьковая сортировка. Теперь остается вопрос — почему он так знаменит? Возможно, ответ действительно заключается в простоте его реализации. Давайте посмотрим, как реализовать пузырьковую сортировку.

Реализация

Реализовать пузырьковую сортировку легко. Вопрос в том, насколько легко? Ну, очевидно, после понимания принципов этого алгоритма каждый разработчик, даже начинающий, может его реализовать. Вот PHP-реализация пузырьковой сортировки.

$input = array(6, 5, 3, 1, 8, 7, 2, 4);
 
function bubble_sort($arr)
{
	$length = count($arr);
 
	for ($i = 0; $i < $length; $i++) {
		for ($j = $length-1; $j > $i; $j--) {
			if ($arr[$j] < $arr[$j-1]) {
				$t = $arr[$j];
				$arr[$j] = $arr[$j-1];
				$arr[$j-1] = $t;
			}
		}
	}
 
	return $arr;
}
 
// 1, 2, 3, 4, 5, 6, 7, 8
$output = bubble_sort($input);

Очевидно, что реализация состоит из нескольких строк кода и двух вложенных циклов.

Сложность: где Bubble Sort по сравнению с другими алгоритмами сортировки

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

Bubble sort в сравнении с быстрой сортировкой, сортировкой слиянием и heapsort в среднем случае

Даже для небольших значений n количество сравнений и обменов может быть огромным.

Bubble sort даже в три раза медленнее быстрой сортировки даже при n = 100, но это проще

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

Применение: 3 классных причины использовать Bubble Sort

Мы видели, что пузырьковая сортировка медленная и неэффективная, но все же используется на практике. Зачем? Есть ли причина использовать этот медленный, неэффективный алгоритм со странным именем? Да, и вот некоторые из них, которые могут быть полезны для любого разработчика.

1. Это легко реализовать

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

2. Потому что библиотека не может помочь

Допустим, вы работаете с JavaScript. Отлично, вы получаете array.sort (), который может помочь в этом: [3, 1, 2] .sort (). Но что произойдет, если вы захотите отсортировать более «сложные» структуры, такие как… некоторые узлы DOM. Здесь у нас есть три узла LI, и мы хотим отсортировать их в некотором порядке. Очевидно, вы не можете сравнить их с оператором «<», поэтому нам нужно найти какое-то специальное решение.

<a href="#">Click here to sort the list</a>
 
<li>node 3</li>
<li>node 1</li>
<li>node 2</li>

Здесь sort () не может помочь нам, и мы должны написать свою собственную функцию. Однако у нас есть только несколько элементов (три в нашем случае). Почему бы не использовать пузырьковую сортировку?

3. Список почти отсортирован

Одна из проблем с пузырьковой сортировкой состоит в том, что она состоит из слишком большого количества перестановок, но что, если мы знаем, что список почти отсортирован?

// almost sorted
[1, 2, 4, 3, 5]

Мы должны поменять только 3 с 4.

Обратите внимание, что в лучшем случае сложность пузырьковой сортировки равна O (n) — быстрее, чем в лучшем случае быстрой сортировки!

Источник: http://www.stoimen.com/blog/2012/02/20/computer-algorithms-bubble-sort/