Как работает сортировка пузырьком?

Question

[Senseich]

Объясните, пожалуйста, как работает сортировка пузырьком? Смысл понятен, но хотелось бы подробно , шаг за шагом, что происходит в каждой строчке и в каждом цикле:
Вот такой код:

<?php

function bubble_sort(&$array)
{
    for ($i=0; $i < count($array); $i++)
    {
        for ($y=($i+1); $y < count($array); $y++)
        {
            if ($array[$i] > $array[$y])
            {
                $c = $array[$i];
                $array[$i] = $array[$y];
                $array[$y] = $c;
            }
        }
    }
}

$arr = array(92, 64, 87, 18, 17, 66, 50, 88, 99, 77);

bubble_sort($arr);

echo '<pre>';
print_r($arr);
echo '</pre>';

?>

P.S.: Прошу без сарказма, я понимаю, что это лёгкая задачка, но я только начинающий.

Answer 1

[McBernar]

Bubble sort — это когда ты циклом проходишь по массиву чисел и сравниваешь пары.
Если первое число больше второго — ты меняешь их местами и начинаешь сначала.

Таким образом за O(n2) операций ты сможешь выстроить всю цепочку.

В коде ровно это и написано — объявляются два цикла, в первом элемент массива стартует с 0, второй с 1, значения сравниваются и если первое больше второго — они меняются местами и массив перезаписывается. И так до тех пор, пока все цепочка не будет отсортирована от меньшего к большему.

Чудовищно долгая сортировка. Банальная бинарная сортировка значительно быстрее пузырька.

Comments

[Senseich]

Меня запутал второй цикл. Вот массив array(92, 64, 87, 18, 17, 66, 50, 88, 99, 77);

Берется нулевой элемент 92, сравнивается с первым 64, меняются местами, получается
array(64, 92, 87, 18, 17, 66, 50, 88, 99, 77); происходит итерация $y++, и потом сравнивается нулевой элемент 64 со вторым 87 получается. Я правильно понимаю? Тут же цикл в цикле, т.е. берется первый элемент из первого цикла и пробегается по второму циклу , потом второй. Не совсем понятно, если честно )

[McBernar]

Senseich: так вы же все правильно написали ) При итерациях Y сравнивается каждое число оставшегося массива с числом i. Когда по y-циклу прошли — переключаем i++ и повторяем весь y-цикл.

[Senseich]

Но число i будет перезаписываться, получается вначале нулевой элемент был 92, потом 64, потом 18, 17. Я почему и попросил прямо по шагам помочь разобрать, вроде и понимаю, а вроде начинаю перебирать не получается )

[McBernar]

Senseich: :) Все просто:
Если 92 больше 64 — они меняются местами (да)
Если 64 больше 87 — они меняются местами (нет)
Если 64 больше 18 — они меняются местами (да)
...

В итоге после первого прохода i-цикла мы получим на нулевом элементе массива наименьшее значение из возможных.

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

[Senseich]

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

Answer 2

[Stalker_RED]

15 Sorting Algorithms in 6 Minutes (пузырек на четвертой минуте)
Visualization and Comparison of Sorting Algorithms (пузырек слева внизу)

Подробная визуализация по шагам
На этом канале есть и другие виды сортировки.

Описание текстом

Answer 3

[dummyman]

Пощупать разницу можно на демке:
math.hws.edu/eck/jsdemo/sortlab.html

Гдето была ссылка на тоже самое, только в 100х больше данных, и там загружал процессор на максимум возможностей, чтобы оценить какая сортировка в каком браузере быстрее. Не могу найти. Найду - прикручу сюда!

Answer 4

[Astrohas]

Вот наиболее наглядный пример https://www.youtube.com/watch?v=lyZQPjUT5B4

Answer 5

[Эдуард]

Вот очень понятное объяснение на youtube вот