Прежде чем перейти к статье, хочу вам представить, экономическую онлайн игру Brave Knights, в которой вы можете играть и зарабатывать. Регистируйтесь, играйте и зарабатывайте!
Здравствуйте, друзья!
Мы продолжаем разбирать максимально простым языком алгоритмы и структуры данных на JavaScript. И сегодня мы поговорим о, пожалуй, самом знаменитом алгоритме, про который слышал каждый разработчик — а именно о сортировке пузырьком (Bubble Sort).
Если вы еще не читали нашу первую статью (про алгоритмы поиска и Big O нотацию), то можете найти ее вот здесь.
А сейчас давайте перейдем к теме статьи.
Алгоритмы сортировки
Как вы знаете, существует множество различных видов алгоритмов в зависимости от типа решаемой задачи: есть алгоритмы поиска, сортировки, хэширования, сжатия данных и т. д.
Алгоритмы сортировки — это алгоритмы для упорядочивания элементов в массиве. Имеется неотсортированный массив, и наша задача его максимально быстро и эффективно отсортировать.
К этой задаче в разное время подходили разными способами, поэтому существует более десятка различных алгоритмов сортировки:
сортировка слиянием (Merge Sort);
сортировка вставками (Insertion Sort);
быстрая сортировка Хоара (Quick Sort);
сортировка Шэлла (Shell Sort);
сортировка подсчетом (Counting Sort);
гномья сортировка (Gnome Sort) и т. д.
Но самый известный алгоритм сортировки – это, конечно же, сортировка пузырьком (Bubble Sort). И это несмотря на то, что данный алгоритм очень медленный и неэффективный, хоть и весьма простой в реализации. К тому же, он практически не применяется в реальной жизни.
Он работает максимально прямолинейно: пробегает по массиву и последовательно сравнивает соседние элементы и меняет их местами, если предыдущий оказывается больше последующего. Таким образом, элементы с большими значениями оказываются в конце списка, а с меньшими остаются в начале. То есть элементы массива как бы «всплывают» до нужной позиции, что очень похоже на поведение пузырька воздуха в воде, именно по этой причине данный алгоритм сортировки и получил свое название.
Посмотреть визуализацию сортировки пузырьком (и многих других алгоритмов) можно вот на этом сайте.
На сортировке пузырьком основаны многие другие методы сортировки, например, шейкерная сортировка (Cocktail Sort) и сортировка расчёской (Comb Sort).
Как работает сортировка пузырьком
Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется перестановка элементов. Проходы по массиву повторяются N-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован.
При каждом проходе алгоритма по внутреннему циклу очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим наибольшим элементом («всплывает» до нужной позиции, как пузырёк в воде), а наименьший элемент перемещается на одну позицию к началу массива.
Вот так выглядит максимально простая реализация данного алгоритма на JavaScript:
const arr = [-5, 23, 7, 5, 3, -12, -29, 21, 54, 35, 0];
function bubbleSort(arr) {
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length; j++) {
if (arr[j] > arr[j + 1]) {
let tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
return arr;
}
console.log(bubbleSort(arr));
Давайте теперь разберем эту реализацию подробнее.
Детальный разбор алгоритма
Итак, у нас имеется неотсортированный массив. Наша задача — отсортировать его по возрастанию, от меньшего к большему.
const arr = [-5, 23, 7, 5, 3, -12, -29, 21, 54, 35, 0];
Создаем функцию bubbleSort и передаем в нее наш неотсортированный массив arr.
const arr = [-5, 23, 7, 5, 3, -12, -29, 21, 54, 35, 0];
function bubbleSort(arr) {
// реализация алгоритма
}
Далее нам нужно создать два цикла for — внешний и внутренний. Один будет вложен в другой. С помощью внутреннего цикла мы будем пробегать по массиву, сравнивать попарно элементы и менять их местами. Таким образом, после каждой итерации внутреннего цикла наибольший элемент будет «всплывать» в конец массива.
Но, пробежавшись лишь один раз по массиву и найдя наибольший элемент, массив всё равно останется неотсортированным.
И вот здесь нам понадобится внешний цикл. Он нужен для того, чтобы данные перестановки были выполнены в итоге для всех элементов массива.
Как только внутренний цикл завершит своё выполнение и мы получим наибольший элемент, далее с помощью внешнего цикла for повторяем эту операцию и получаем уже два отсортированных элемента в конце массива. Далее этот процесс повторяется до полной сортировки массива.
Итак, сначала создадим внешний цикл for.
Внутри него инициализируем счётчик и установим его исходное значение, которое будет равно нулю, так как мы собираемся перебирать массив, начиная с самого первого элемента.
let i = 0;
Наш цикл будет выполняться до тех пор, пока не пройдет по всем элементам массива. В качестве конечной точки мы используем значение arr.length, которое возвращает количество элементов в массиве. Так как массив arr начинается с нулевого индекса, то мы используем при сравнении знак «<».
i < arr.length;
После каждой итерации цикла увеличиваем значение переменной i на единицу (i++).
const arr = [-5, 23, 7, 5, 3, -12, -29, 21, 54, 35, 0];
function bubbleSort(arr) {
for (let i = 0; i < arr.length; i++) {
}
}
Далее нам необходимо создать еще один цикл for и вложить его внутрь уже созданного.
Как вы помните, внутренний цикл отвечает за поиск наибольшего элемента, и именно в нём мы меняем элементы местами.
Поэтому создаём еще один цикл for. Как и в прошлый раз, при инициализации счетчика установим его значение, равное 0.
В качестве конечной точки мы также будем использовать значение arr.length, которое возвращает количество элементов в массиве.
После каждой итерации цикла увеличиваем значение переменной j на единицу.
const arr = [-5, 23, 7, 5, 3, -12, -29, 21, 54, 35, 0];
function bubbleSort(arr) {
// Внешний цикл for (повторяем вложенный цикл для каждого элемента массива)
for (let i = 0; i < arr.length; i++) {
// Внутренний цикл for (находим наибольший элемент из неотсортированных)
for (let j = 0; j < arr.length; j++) {
// сравниваем элементы массива и меняем их местами
}
}
Далее с помощью условной конструкции if создаем проверку: если элемент массива по индексу j больше элемента массива по индексу j + 1, то необходимо поменять их местами. Как вы помните, мы сортируем элементы в массиве по возрастанию, поэтому наибольшие элементы собираются в конце массива.
const arr = [-5, 23, 7, 5, 3, -12, -29, 21, 54, 35, 0];
function bubbleSort(arr) {
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length; j++) {
// Сравниваем соседние элементы массива
if (arr[j] > arr[j + 1]) {
// меняем соседние элементы массива местами
}
}
}
Реализуем перестановку двух элементов местами через третью переменную. Для этого создадим временную переменную tmp (от англ. temporary — временный). В нее мы положим значение элемента массива по индексу j (arr[j]). Сохранив таким образом значение arr[j] в третьей переменной, мы уже можем присвоить arr[j] значение соседнего элемента arr[j + 1]. А затем присваиваем arr[j + 1] значение переменной tmp.
В итоге два соседних элемента в массиве поменялись местами.
function bubbleSort(arr) {
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length; j++) {
if (arr[j] > arr[j + 1]) {
// Меняем элементы местами с помощью третьей переменной
let tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
}
Теперь нам осталось лишь вернуть отсортированный массив arr после выполнения внутреннего и внешнего цикла for.
А также вызвать функцию bubbleSort, передав в нее неотсортированный массив arr, и затем вывести результат выполнения функции в консоль.
function bubbleSort(arr) {
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length; j++) {
if (arr[j] > arr[j + 1]) {
let tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
return arr; // Возвращаем отсортированный массив
}
console.log(bubbleSort(arr)); // Выводим результат в консоль
Пару слов про оценку сложности алгоритма.
В предыдущей статье мы с вами уже затронули тему оценки сложности алгоритмов и поговорили про так называемую Биг О нотацию, которая описывает худший возможный случай выполнения алгоритма.
Если мы говорим, что пузырьковая сортировка выполняется за время O(n^2), это значит, что медленнее она точно работать не будет. Здесь n, как вы помните, это количество операций, которое предстоит выполнить алгоритму.
В данном случае, сортировка пузырьком выполняется за квадратичное время, потому что мы имеем два вложенных друг в друга цикла for, которые выполняют одинаковое количество операций.
Иными словами, в худшем случае, мы передаем в функцию bubbleSort массив, отсортированный по убыванию, при этом нам нужно отсортировать его по возрастанию. В таком случае, нам нужно пройти по нему n раз (за это, как вы помните, отвечает внешний цикл).
Далее на каждой итерации цикла мы в худшем случае проведём n-1 сравнений, т.е. если у нас в массиве 4 элемента, то мы должны провести 3 сравнения.
В данном случае единицей можно пренебречь, и, учитывая два цикла, один из которых вложен в другой, количество операций будет n * n или n^2.
Помимо худшего возможного случая выполнения (Big О), при оценке скорости работы алгоритма также выделяют среднее время выполнения алгоритма — Биг Тета (Big Θ) и лучшее время — Биг Омега (Big Ω).
В среднем, сортировка пузырьком выполняется за квадратичное время, поэтому ожидаемая производительность алгоритма будет Θ(n^2).
В лучшем случае, мы передаем в функцию bubbleSort уже отсортированный по возрастанию массив, поэтому алгоритму потребуется выполнить лишь один проход по массиву, что представляет собой константное время.
Но алгоритму всё равно придется выполнить n сравнений, поэтому здесь мы получим 1 * n или n операций. Таким образом, в лучшем случае алгоритм сортировки пузырьком будет выполняться за линейное время — Ω(n).
Что, как вы помните, всё равно достаточно медленно, поэтому сортировка пузырьком — крайне неэффективный алгоритм.
Также, чтобы получить линейное время выполения алгоритма, нам необходимо слегка модифицировать текущую реализацию сортировки пузырьком.
Вот так будет выглядешь наш алогритм, у которого есть шанс выполниться за линейное время:
function bubbleSort(arr) {
let isSorted; // Добавим переменную, отвечающую на вопрос - отсортирован наш массив или нет.
for (let i = 0; i < arr.length; i++) {
isSorted = true; // Предположим, что наш массив отсортирован.
for (let j = 0; j < arr.length - i; j++) { // так как при каждой итерации цикла наибольший элемент перемещается в конец массива, нам нет нужды выполнять проверку для уже отсортированных элементов.
if (arr[j] > arr[j + 1]) {
let tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
isSorted = false; // Так как мы поменяли элементы местами, значит, наш массив не отсортирован. Устанавливаем значение false.
}
}
if (isSorted) return arr; // Если isSorted === true, значит наш массив отсортирован, и мы сразу же возвращаем его.
}
return arr;
}
Также при оценке сложности алгоритмов, оценивают их сложность по памяти, т.е. сколько памяти будет в итоге задействовано при работе алгоритма.
Здесь нас интересует только худший случай, поэтому мы будем использовать Биг О нотацию.
Сортировка пузырьком расходует постоянное количество памяти. Дело в том, что мы сортируем уже имеющийся массив и не создаём дополнительных структур данных, в которых теоретически могли что-нибудь хранить.
Поэтому сложность нашего алгоритма по памяти будет константной и записывается как O(1).
А вот если бы мы, например, создали пустой массив и добавляли в него отсортированные элементы, то сложность такого алгоритма была бы уже линейной или O(n), потому что количество дополнительной памяти росло бы пропорционально количеству элементов во входящем массиве данных.
На этом мы закончили вторую статью из нашего цикла статей по алгоритмам. Спасибо за внимание и до новых встреч.
