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

Пошаговый пример

Ожидаемый результат

Сортировать по возрастанию
Ввод: [4, 2, 5, 1, 3, 6]
Выход: [1, 2, 3, 4, 5, 6]

Первая итерация
сравнивает первый элемент со вторым элементом, поменять местами с 4 ›2
[4, 2 , 5, 1, 3, 6] → [2, 4, 5, 1, 3, 6]
сравнить второй элемент с третьим элемент, не менять местами, поскольку 4 ‹5
[2, 4, 5, 1, 3, 6] → [ 2, 4, 5, 1, 3, 6]
сравнить третий элемент с четвертым, поменять местами, поскольку 5 ›3 < br /> [2, 4, 5, 1, 3, 6] → [2, 4, 1, 5 , 3, 6]
сравнить четвертый элемент с пятым, поменять местами с 5 ›3
[2, 4, 1, 5 , 3, 6] → [2, 4, 1, 3, 5, 6]
сравнить пятый элемент с шестым элементом , не менять местами, поскольку 5 ‹6
[2, 4, 1, 3, 5, 6] → [2 , 4, 1, 3, 5, 6]

Вторая итерация

не меняйте местами
[2, 4, 1, 3, 5, 6] → [2, 4 , 1, 3, 5, 6]
поменять местами
[2, 4, 1, 3, 5, 6] → [2, 1, 4, 3, 5, 6]
поменять местами
[2, 1, 4, 3, 5, 6] → [2, 1, 3, 4, 5, 6]
не менять местами < br /> [2, 1, 3, 4, 5, 6] → [2, 1, 3, 4, 5, 6]
не менять местами
[2, 1, 3, 4, 5, 6] → [2 , 1, 3, 4, 5, 6]

Третья итерация

поменять местами
[2, 1, 3, 4, 5, 6] → [1, 2 , 3, 4, 5, 6]
не менять местами
[1, 2, 3, 4, 5, 6] → [1, 2, 3, 4, 5, 6]
не менять местами
[1, 2, 3, 4 , 5, 6] → [1, 2, 3, 4, 5, 6]
не надо t поменять местами
[1, 2, 3, 4, 5, 6] → [1, 2, 3, 4, 5 , 6]

Неоптимизированное решение

Даже когда массив отсортирован, с неоптимизированным решением он будет перебирать массив за время O (n²). Это означает, что в этом тестовом примере у нас будет еще 3 итерации (всего 6), каждая из которых будет проверять свопы по 5 раз. Это потому, что неоптимизированное решение имеет внешний цикл для каждого элемента массива и внутренний цикл для длины массива-1, поскольку мы проверяем элемент, а также элемент после него, поэтому нам нечего будет проверять против последнего элемента.

Код

Неоптимизированный

function bubblesort(arr){ 
    for (let i = 0; i < arr.length; i++) {
        for (let j = 0; j < arr.length - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                let temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    return arr
}

Давайте пройдемся через это!

Мы устанавливаем цикл for на выполнение равное количество раз, равное длине нашего массива. Внутри этого for цикла мы устанавливаем другой for цикл на выполнение на 1 раз меньше, чем длина нашего массива. Это означает, что если наш массив имеет длину 6, наш внутренний цикл будет выполняться 6 * 5 раз (5 раз для каждого внешнего цикла).

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

Во втором цикле мы проверяем, является ли элемент с этим индексом ›элементом с индексом после.

Если это так, нам нужно поменять местами значения, хранящиеся в этих индексах. Из-за этого у нас есть переменная temp для хранения значения в нашем текущем индексе, чтобы оно не потерялось во время переназначения.

Таким образом, temp будет равно значению в arr[j], arr[j] будет равно значению в arr[j+1] (элемент после него), а arr[j+1] будет равен значению temp (которое было предыдущим значением arr[j]).

Сложность времени

Теперь, поскольку эти циклы будут выполняться всегда, независимо от того, отсортирован ли массив или нет, или даже если передан отсортированный массив, временная сложность составляет O (n²). Мы можем оптимизировать этот код, проверив, отсортирован ли массив и выйдя из цикла.

Оптимизировано

function bubblesort(arr){
    for (let i = 0; i < arr.length; i++) {
        let swapped = false;
        for (let j = 0; j < arr.length; j++) {
            if (arr[j] > arr[j + 1]) {
                swapped = true;
                let temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        if (swapped !== true) break;
    }
    return arr
}

В оптимизированном решении у нас есть дополнительная переменная swapped. Он устанавливается в значение false в начале первого for цикла. Во внутреннем цикле, если элемент необходимо поменять местами, swapped устанавливается в значение true, таким образом, как только мы выйдем из внутреннего цикла и вернемся к нашему внешнему циклу, мы проверим, нужно ли поменять местами какой-либо из элементов.

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

Сложность времени и пространства

В лучшем случае массив уже отсортирован, а временная сложность будет O (n), он будет проходить цикл на всю длину массива, а затем прерывается. В худшем случае массив находится в обратном порядке, тогда временная сложность по-прежнему O (n²).

Мы выполняем сортировку на месте, что означает, что мы только перемещаем / переупорядочиваем значения внутри переданного массива. Мы назначаем одну или две переменные temp и / или swapped. Это дает нам пространственную сложность O (1), что означает, что она постоянна (ввод не влияет на то, сколько места в памяти он занимает). Если бы мы выполняли неразрушающую сортировку, что означало бы, что мы не изменяли бы массив, который передается (путем создания копии массива и сортировки + возврата копии), сложность пространства была бы O (n), она бы точно масштабировалась к размеру переданного массива.

В заключении…

Стоит отметить, что при рассмотрении оптимизированной пузырьковой сортировки я часто видел, как люди использовали цикл do...while, а не цикл for. Я больше привык к for циклам, но do...while кажется более информативным в отношении того поведения, которое мы хотим (только цикл, когда элементы нужно было менять местами).

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