Алгоритм и реализация пузырьковой сортировки
Один из алгоритмов сортировки носит именно такое название. Его суть очень проста.
Предположим, что у нас есть массив чисел, которые нужно отсортировать от меньшего к большему. Представим каждое число в виде пузырька. Чем больше число-тем больше размер пузырька.
Теперь будет сортировать их по следующему принципу:
Берем первый и второй пузырьки. Если первый больше - то меняем их местами.
Затем берём второй и третий и также сравниваем их. Если второй больше третьего-то меняем местами второй и третий.
И так далее.
После того, как сравним предпоследний последний элементы - начинаем всё сначала, и делаем такой обход столько раз(максимум), сколько элементов в массиве минус один.
Схематично это выглядит так:
В чём основной минус данного подхода - такой алгоритм будет медленно работать при больших объёмах данных. Он уместен для небольших массивов, просто для обучения алгоритмам и его очень часто спрашивают на собеседованиях. Почему? Незнаю. Да, второе по популярности - это рекурсивная функция.
Ну и сам код на PHP:
$unsorted = [3, 12, 5, 6, 18, 15];
print_r($unsorted);
$sorted = bubbleSorting($unsorted);
print_r($sorted);
function bubbleSorting($data)
{
$array_length = count($data);
$iterations_count = $array_length - 1;
//обходим массив столько раз, сколько в нём элементов
$i = 0;
while($i < $array_length) {
$sorted = FALSE;
$y = 0;
while ($y < $iterations_count) {
//сравниваем соседние элементы массива
if ($data[$y] > $data[$y + 1]) {
$sorted = TRUE;
//меняем их местами
list($data[$y], $data[$y + 1]) = [
$data[$y + 1],
$data[$y]
];
}
$y++;
}
$iterations_count--;
if (!$sorted) {
//элементы не менялись местами, значит массив отсортирован
return $data;
}
$i++;
}
return $data;
}
Код на pastebin https://pastebin.com/YjDLMJTu