Сортування бульбашкою - JavaScript (Bubble Sort)

Сортування бульбашкою (Bubble Sort) також іноді називають сортуванням простими обмінами.

Загалом єдиною перевагою цього алгоритму є те, що він простий у реалізації. Сам по собі він не є ефективним, має складність O(n²) і на практиці не використовується. Але знати його не завадить, адже на його основі створено інші складніші й оптимізованіші алгоритми - сортування перемішуванням (Cocktail sort), сортування купою (Heapsort), швидке сортування (Quicksort).

Суть алгоритму в порівнянні пари сусідніх елементів - якщо вони стоять у неправильному порядку, то їх міняють місцями. Щоб впорядкувати таким чином увесь масив завдовжки N, доведеться пройтися по ньому N-1 раз (останній елемент уже буде відсортовано на попередній ітерації, тому для нього прохід не потрібен). Також за кожен прохід у кінець масиву "спливає" при сортуванні за зростанням - найбільше число, за спаданням - найменше. А отже, на наступній ітерації його можна вже не перевіряти.

Візуалізація алгоритму сортування бульбашкою

У першому наближенні алгоритм для сортування за зростанням виглядає так:

function bubbleSort(arr) {
    for (var i = 0, endI = arr.length - 1; i < endI; i++) {
        for (var j = 0, endJ = endI - i; j < endJ; j++) {
            if (arr[j] > arr[j + 1]) {
                var swap = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = swap;
            }
        }
    }
    return arr;
}

Але в такому вигляді ніяк не враховується, який масив надійшов на вхід, і навіть для вже відсортованого масиву програма повинна буде виконати всі ітерації циклів.

Її можна оптимізувати, додавши прапор, що відстежує перестановку елементів - якщо за черговий прохід масивом не відбулося жодної, значить, масив уже відсортовано. Код тепер матиме такий вигляд:

function bubbleSort(arr) {
    for (var i = 0, endI = arr.length - 1; i < endI; i++) {
        var wasSwap = false;
        for (var j = 0, endJ = endI - i; j < endJ; j++) {
            if (arr[j] > arr[j + 1]) {
                var swap = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = swap;
                wasSwap = true;
            }
        }
        if (!wasSwap) break;
    }
    return arr;
}

Ну і наостанок перепишемо наш алгоритм на новий синтаксис ES6 і позбудемося додаткової змінної:

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;
};