Сегодня мы будем обсуждать алгоритмы, а точнее алгоритм пузырьковой сортировки. Когда я впервые начал свой путь программирования, я думал, что смогу обойтись без глубокого погружения в такие темы, как шаблоны проектирования и алгоритмы. Вскоре я понял, что эти темы не только важны, но и очень полезны, когда дело доходит до более глубокого понимания написания кода. Так зачем изучать алгоритмы? В программировании алгоритмы имитируют реальные жизненные проблемы и предлагают реальные решения этих проблем. Алгоритмы не только помогают углубить ваше понимание написания кода, но и помогают решать распространенные проблемы, с которыми вы столкнетесь при создании приложений. Это отличные умственные упражнения, и они заставляют вас планировать заранее, прежде чем погрузиться прямо в ваш код. Давайте рассмотрим распространенный алгоритм сортировки — алгоритм пузырьковой сортировки.

Что такое алгоритм пузырьковой сортировки?

Это алгоритм сортировки, который многократно проходит по списку, сравнивает соседние элементы и меняет их местами, если они расположены не в правильном порядке. Этот шаг повторяется до тех пор, пока список не будет полностью отсортирован. Алгоритм получил свое название из-за того, что меньшие элементы «пузырятся» в верхней части списка.

Шаг за шагом:

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

Когда следует использовать алгоритм пузырьковой сортировки?

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

Проще говоря, этот алгоритм неэффективен для сортировки больших списков, потому что, если у нас есть список размером 10, нам, возможно, придется перебрать этот список 10² раз. Вы можете себе представить, что с большими списками этот алгоритм может занять некоторое время. Хотя временная сложность может быть причиной для беспокойства, этот алгоритм очень прост в реализации и может быть полезен в определенных ситуациях.

Пример:

Давайте посмотрим на алгоритм пузырьковой сортировки в действии.

function bubbleSort(arr) {
    let swapped;
        do {
            swapped = false;
            for (let i = 0; i < arr.length; i++) {
                if (arr[i] > arr[i + 1]) {
                    let temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                    swapped = true;
                }
            }
        } while (swapped);
    return arr;
}

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

Убедимся, что это работает!

var nums = [2,7,12,45,43,67,98,43,5,23,4,9,34,21,34,5];

console.log(bubbleSort(nums));
// returns [2, 4, 5, 5, 7, 9, 12, 21, 23, 34, 34, 43, 43, 45, 67, 98]

Отличный! Наш алгоритм пузырьковой сортировки работает именно так, как мы хотели.

Заключение

В этой статье мы узнали об алгоритме пузырьковой сортировки. Мы обсудили, как это работает, когда полезно, а когда нет, и рассмотрели пример алгоритма с использованием JavaScript. Я буду продолжать изучать алгоритмы и внедрять их в свои проекты, и я надеюсь, что вы сделаете то же самое! Продолжайте учиться и удачного кодирования!