Сортировка пузырьком

Сортировку пузырьком (Bubble Sort) также иногда называют сортировкой простыми обменами.

Он берет два первых элемента массива, сравнивает их и расставляет по порядку. Затем происходит смещение на один элемент вправо и сравниваются уже второй и третий элементы. И так далее до конца массива.

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

Пример кода:

            const bubbleSort = arr => {

            for (let i = 0, endI = arr.length - 1; i < endI; i++) {
                let wasSwap = false;

                for (let j = 0, endJ = endI - i; j < endJ; j++) {
                    if (arr[j] > arr[j + 1]) {
                        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
                        wasSwap = true;
                    }
                }

                if (!wasSwap) break;
            }

            return arr;
        };

– Первый цикл отслеживает индекс последнего всплывшего элемента. На каждой итерации он будет уменьшаться.
– Второй цикл – это индекс активного элемента на текущей итерации. Он будет начинаться с нуля и продолжаться до элементов, "всплывших" на предыдущих итерациях. Так как они уже отсортированы, не имеет смысла снова их сравнивать.

Сложность

Пузырьковая сортировка является устойчивой, а ее временная сложность составляет O(N²) в худшем случае. Это означает, что для массива с n элементами нужно совершить n2 операций: для каждого из элементов приходится сделать проход по всем остальным элементам массива. Реальное значение чуть меньше чем n2 , но при расчете сложности алгоритма все коэффициенты отбрасываются. В лучшем случае, если массив уже отсортирован, потребуется всего n операций.

Если у вас возникли трудности с понимаем работы алгоритма, можно посмотреть его визуализацию на видео: