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

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

Самый простой, но не самый эффективный алгоритм.

Контекст: мы начали говорить об алгоритмах сортировки — смысл в том, что есть алгоритмы, которые помогают упорядочить разные неорганизованные данные. И данные, и алгоритмы могут быть разными, поэтому разработчики разбираются в этих алгоритмах, чтобы подобрать лучшее. 

Что разбираем: пузырьковую сортировку — самый простой способ отсортировать массив, написав всего 6 строк кода. Она самая простая, но не самая эффективная. 

Зачем это нужно: пузырьковая сортировка проще остальных, поэтому изучение всех сортировок лучше начинать именно с неё — так будет легче понять, что происходит в остальных алгоритмах. А ещё пузырьковая сортировка применяется внутри других, более эффективных алгоритмов.

Принцип работы

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

Алгоритм выглядит так:

  1. Берём самый первый элемент массива и сравниваем его со вторым. Если первый больше второго — меняем их местами с первым, если нет — ничего не делаем.
  2. Затем берём второй элемент массива и сравниваем его со следующим — третьим. Если второй больше третьего — меняем их местами, если нет — ничего не делаем.
  3. Проходим так до предпоследнего элемента, сравниваем его с последним и ставим наибольший из них в конец массива. Всё, мы нашли самое большое число в массиве и поставили его на своё место.
  4. Возвращаемся в начало алгоритма и делаем всё снова точно так же, начиная с первого и второго элемента. Только теперь даём себе задание не проверять последний элемент — мы знаем, что теперь в конце массива самый большой элемент. 
  5. Когда закончим очередной проход — уменьшаем значение финальной позиции, до которой проверяем, и снова начинаем сначала.
  6. Так делаем до тех пор, пока у нас не останется один элемент.

Пример

Возьмём массив из шести чисел и сделаем первый прогон:

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

После первого прогона у нас «всплыл» самый большой элемент массива (число 11) и отправился в конец. После второго прогона на предпоследнем месте будет стоять число 9 — оно «всплывёт» наверх как самое большое число из оставшихся, потому что последние элементы мы не проверяем.

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

Работает это примерно так:

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

Эффективность работы

Этот алгоритм считается учебным и в чистом виде на практике почти не применяется. Дело в том, что среднее количество проверок и перестановок в массиве — это количество элементов в квадрате. Например, для массива из 10 элементов потребуется 100 проверок, а для массива из 100 элементов — уже в сто раз больше, 10 000 проверок. 

Получается, что если у нас в массиве будет 10 тысяч элементов (а это не слишком большой массив с точки зрения реальных ИТ-задач), то для его сортировки понадобится 100 миллионов проверок — на это уйдёт какое-то время. А что, если сортировать нужно несколько раз в секунду? 

👉 В программировании эффективность работы алгоритма в зависимости от количества элементов n обозначают так: O(n). В нашем случае эффективность работы пузырьковой сортировки равна O(n²). По сравнению с другими алгоритмами это очень большой показатель (чем он больше — тем больше времени нужно на сортировку).

Реализация в коде

Запустите этот код в консоли браузера, чтобы посмотреть на работу алгоритма целиком:

// исходный массив
var arr = [3,1,9,8,11,6]

// определяем количество прогонов
// перебирать будем всё до предпоследнего элемента, каждый раз сдвигая его ближе к началу
for (let j = arr.length - 1; j > 0; j--) {
    // основной цикл внутри каждого прогона
    // перебираем все элементы от первого до последнего в прогоне, который мы определили выше
    for (let i = 0; i < j; i++) {
      // если текущий элемент больше следующего
      if (arr[i] > arr[i + 1]) {
        // запоминаем значение текущего элемента
        let temp = arr[i];
        // записываем на его место значение следующего
        arr[i] = arr[i + 1];
        // а на место следующего ставим значение текущего, тем самым меняем их местами
        arr[i + 1] = temp;
      }
      // выводим текущее состояние массива в консоль
      // это необязательный шаг, он здесь для наглядности
      console.log(arr);
    }
  }

Что дальше

В следующей статье сделаем красивую визуализацию этого алгоритма на HTML и CSS — покажем, как числа всплывают как пузырьки наверх.

Текст:

Михаил Полянин

Редактор:

Максим Ильяхов

Художник:

Даня Берковский

Корректор:

Ирина Михеева

Вёрстка:

Кирилл Климентьев

Соцсети:

Олег Вешкурцев

Получите ИТ-профессию
В «Яндекс Практикуме» можно стать разработчиком, тестировщиком, аналитиком и менеджером цифровых продуктов. Первая часть обучения всегда бесплатная, чтобы попробовать и найти то, что вам по душе. Дальше — программы трудоустройства.
Начать карьеру в ИТ
Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию
Еще по теме
Haskell — ленивый язык программирования
Haskell — ленивый язык программирования

Он сам решает, что и когда нужно посчитать.

easy
Вам мало языка C? Попробуйте C++
Вам мало языка C? Попробуйте C++

Шустрый, мощный, весь обвешан классами.

medium
Зарплата 113 тысяч за то, чтобы ломать программы
Зарплата 113 тысяч за то, чтобы ломать программы

Работа тестировщика как она есть.

easy
Что такое Java и зачем он нужен

Это как JavaScript? Нет!

easy
Что такое SVG-графика и зачем она нужна
Что такое SVG-графика и зачем она нужна

Простая рисовалка на CSS.

easy
Саша Селезнёва: в «Яндекс» из Саратова в 20 лет
Саша Селезнёва: в «Яндекс» из Саратова в 20 лет

О работе гуманитария в ИТ

easy
Как русские хакеры взломали Clubhouse
Как русские хакеры взломали Clubhouse

Краткий конспект подкаста

easy
Для чего на сервере нужен файл .htaccess
Для чего на сервере нужен файл .htaccess

И что с ним можно сделать полезного

medium
Что такое микросервисы
Что такое микросервисы

Разбиваем программу на сотни частей.

medium
Богдан Овсиюк: из пограничника в тестировщики за полгода
Богдан Овсиюк: из пограничника в тестировщики за полгода

История выпускника Практикума.

medium
Почему процессоры Apple M1 такие быстрые
Почему процессоры Apple M1 такие быстрые

И правда ли они такие быстрые? И на что это влияет?

easy
Вместо Dropbox: ваше собственное облачное хранилище файлов
Вместо Dropbox: ваше собственное облачное хранилище файлов

Продолжение саги про облачные бэкапы

medium
Зачем вам jQuery
Зачем вам jQuery

Каждый год говорят о том, что jQuery уже не тот, но продолжают его использовать. Почему? Вот почему.

medium
easy