Сегодня мы будем обсуждать алгоритмы, а точнее алгоритм пузырьковой сортировки. Когда я впервые начал свой путь программирования, я думал, что смогу обойтись без глубокого погружения в такие темы, как шаблоны проектирования и алгоритмы. Вскоре я понял, что эти темы не только важны, но и очень полезны, когда дело доходит до более глубокого понимания написания кода. Так зачем изучать алгоритмы? В программировании алгоритмы имитируют реальные жизненные проблемы и предлагают реальные решения этих проблем. Алгоритмы не только помогают углубить ваше понимание написания кода, но и помогают решать распространенные проблемы, с которыми вы столкнетесь при создании приложений. Это отличные умственные упражнения, и они заставляют вас планировать заранее, прежде чем погрузиться прямо в ваш код. Давайте рассмотрим распространенный алгоритм сортировки — алгоритм пузырьковой сортировки.
Что такое алгоритм пузырьковой сортировки?
Это алгоритм сортировки, который многократно проходит по списку, сравнивает соседние элементы и меняет их местами, если они расположены не в правильном порядке. Этот шаг повторяется до тех пор, пока список не будет полностью отсортирован. Алгоритм получил свое название из-за того, что меньшие элементы «пузырятся» в верхней части списка.
Шаг за шагом:
- Сравните первые два элемента в списке. Если первое больше второго, поменяйте их местами.
- Сравните второй и третий элементы в списке. Если второе больше третьего, поменяйте их местами.
- Продолжайте этот процесс, пока не дойдете до конца списка.
- Если во время текущего прохода были сделаны какие-либо замены, повторите процесс еще раз с начала списка.
Когда следует использовать алгоритм пузырьковой сортировки?
Алгоритм пузырьковой сортировки отлично подходит для сортировки списков меньшего размера. Это связано с тем, что этот алгоритм имеет временную сложность 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. Я буду продолжать изучать алгоритмы и внедрять их в свои проекты, и я надеюсь, что вы сделаете то же самое! Продолжайте учиться и удачного кодирования!