Вступление

Пузырьковая сортировка, иногда также называют Погружение Сортировки является одним из наиболее широко известных алгоритмов сортировки. Обычно это один из первых алгоритмов сортировки, с которым сталкиваются студенты CS, из-за его простоты и того факта, что он довольно интуитивно понятен и легко переводится в код.

Однако этот простой алгоритм показал низкую производительность в реальных задачах. Особенно по сравнению с более быстрыми, более популярными и широко используемыми алгоритмами, такими как Quicksort или Merge Sort. Вот почему пузырьковая сортировка используется в первую очередь как обучающий инструмент.

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

Кроме того, мы реализуем один из его вариантов - сортировку с помощью коктейльного шейкера, чтобы оптимизировать его.

Пузырьковая сортировка

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

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

Это делается снова и снова, пока все элементы в коллекции не будут отсортированы. Давайте посмотрим на визуальное представление того, как работает пузырьковая сортировка:

{.ezlazyload}

Взглянув на элемент со значением 8 , мы можем увидеть, как он «всплывает» из начала массива в свое надлежащее место. Отсюда и название «пузырьковая сортировка».

Реализация пузырьковой сортировки

Теперь, когда мы рассмотрели идею пузырьковой сортировки, мы можем начать с реализации:

 function bubbleSort(inputArr) { 
 let n = inputArr.length; 
 
 for(let i = 0; i < n; i++) { 
 for(let j = 0; j < n; j++) { 
 // Comparing and swapping the elements 
 if(inputArr[j] > inputArr[j+1]){ 
 let t = inputArr[j]; 
 inputArr[j] = inputArr[j+1]; 
 inputArr[j+1] = t; 
 } 
 } 
 } 
 return inputArr; 
 } 

Реализация довольно интуитивна. Мы перебираем массив n раз с помощью for , где n - длина массива. Для каждой итерации мы «пузыри» элемент на его правильное место. Это делается с помощью другого for который сравнивает элемент с соседним, при необходимости переключая их.

Наконец, мы возвращаем отсортированный массив. Заполним массив и отсортируем его:

 let inputArr = [5,1,4,2,8]; 
 bubbleSort(inputArr); 
 console.log(inputArr); 

Запуск этого кода даст:

 (5) [1, 2, 4, 5, 8] 

Давайте посмотрим, как это делается с конкретными значениями:

Первая итерация:

[ 5 , 1 , 4, 2, 8] -> [ 1 , 5 , 4, 2, 8] - Мы меняем местами 5 и 1, так как 5> 1
[1, 5 , 4 , 2, 8] -> [1, 4 , 5 , 2, 8] - Мы меняем местами 5 и 4, так как 5> 4
[1, 4, 5 , 2 , 8] -> [1, 4, 2 , 5 , 8] - Мы меняем местами 5 и 2, так как 5> 2
[1, 4, 2, 5 , 8 ] -> [1, 4, 2, 5 , 8 ] - Без изменений, поскольку 5 <8

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

[ 1 , 4 , 2, 5, 8] -> [ 1 , 4 , 2, 5, 8] - Без изменений, поскольку 1 <4
[1, 4 , 2 , 5, 8] -> [1, 2 , 4 , 5, 8] - Мы меняем местами 4 и 2, так как 4> 2
[1, 2, 4 , 5 , 8] -> [1, 2, 4 , 5 , 8] - Без изменений, поскольку 4 <5
[1, 2, 4, 5 , 8 ] -> [1, 2, 4, 5 , 8 ] - Без изменений, поскольку 5 <8

Массив сортируется в течение двух итераций, однако наш алгоритм продолжит выполнение n раз, снова и снова сравнивая все элементы. Это потому, что мы сказали ему перебирать inputArr.length раз.

Пузырьковая сортировка неэффективна сама по себе, особенно с таким недостатком. Однако есть две вещи, которые мы можем сделать, чтобы его оптимизировать.

Оптимизация

Первая оптимизация, которую мы можем реализовать, - это завершить алгоритм, если массив отсортирован, т.е. свопы не производятся. Это можно сделать с помощью boolean флага. Каждый раз, когда мы меняем местами какие-либо элементы, устанавливается значение true :

 function bubbleSort(inputArr) { 
 let n = inputArr.length; 
 let sorted = false; 
 
 while (!sorted) { 
 sorted = true; 
 for(let i = 0; i < n; i++){ 
 if(inputArr[i] > inputArr[i+1]){ 
 let t = inputArr[i]; 
 inputArr[i] = inputArr[i+1]; 
 inputArr[i+1] = t; 
 sorted = false; 
 } 
 } 
 } 
 return inputArr; 
 } 

Как только мы закончим итерации через массив, и не было сделано никаких свопы, то в while цикл будет остановить цикл и массив возвращается.

Давайте снова заполним массив и отсортируем его:

 let inputArr = [5,1,4,2,8]; 
 bubbleSort(inputArr); 
 console.log(inputArr); 

Этот код приводит к:

 [1, 2, 4, 5, 8] 

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

Это означает, что на каждой итерации нам действительно не нужно смотреть на последний элемент, поскольку мы знаем, что он находится в нужном месте. Таким образом, на k-й итерации нам действительно нужно взглянуть на n-k + 1 итерацию:

 function bubbleSort(inputArr) { 
 
 let n = inputArr.length; 
 let sorted = false; 
 let numOfIterations = 0; 
 
 while(!sorted) { 
 sorted = true; 
 for(let i = 0; i < n-numOfIterations+1; i++){ 
 if(inputArr[i] > inputArr[i+1]){ 
 let t = inputArr[i]; 
 inputArr[i] = inputArr[i+1]; 
 inputArr[i+1] = t; 
 sorted = false; 
 numOfIterations++; 
 } 
 } 
 } 
 return inputArr; 
 } 

Давайте снова заполним массив и отсортируем его:

 let inputArr = [5,1,4,2,8]; 
 bubbleSort(inputArr); 
 console.log(inputArr); 

Этот код приводит к:

 (5) [1, 2, 4, 5, 8] 

Сортировка коктейль-шейкер и пузырьковая сортировка

Еще одна оптимизация пузырьковой сортировки - это производный от нее вариант, называемый сортировкой с помощью шейкер-коктейля , также известный как двунаправленная пузырьковая сортировка или просто коктейльная сортировка .

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

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

Давайте продолжим и реализуем алгоритм:

 function cocktailShakerSort(inputArr) { 
 
 let n = inputArr.length; 
 let sorted = false; 
 
 while (!sorted) { 
 sorted = true; 
 for (let i = 0; i < n - 1; i++) { 
 if (inputArr[i] > inputArr[i + 1]){ 
 let tmp = inputArr[i]; 
 inputArr[i] = inputArr[i + 1]; 
 inputArr[i+1] = tmp; 
 sorted = false; 
 } 
 } 
 
 if (sorted) 
 break; 
 sorted = true; 
 
 for (let j = n - 1; j > 0; j--) { 
 if (inputArr[j-1] > inputArr[j]) { 
 let tmp = inputArr[j]; 
 inputArr[j] = inputArr[j + 1]; 
 inputArr[j+1] = tmp; 
 sorted = false; 
 } 
 } 
 } 
 return inputArr; 
 } 

Первая часть аналогична обычной пузырьковой сортировке. Хотя, пройдя вперед, мы идем назад. Сначала мы проверяем, отсортирован ли массив с помощью предыдущего прямого прохода. Если нет, идем назад, при необходимости меняя местами. Если свопы не выполняются, алгоритм завершается и возвращается результат.

Если бы мы не проверяли свопы на втором проходе, нам пришлось бы пропустить дополнительное время вперед, чтобы проверить, отсортирован ли массив.

Давайте посмотрим на ручной пример из прошлого - на этот раз с коктейльным шейкером:

[ 5 , 1 , 4, 2, 8] -> [ 1 , 5 , 4, 2, 8] - Мы меняем местами 5 и 1, так как 5> 1
[1, 5 , 4 , 2, 8] -> [1, 4 , 5 , 2, 8] - Мы меняем местами 5 и 4, так как 5> 4
[1, 4, 5 , 2 , 8] -> [1, 4, 2 , 5 , 8] - Мы меняем местами 5 и 2, так как 5> 2
[1, 4, 2, 5 , 8 ] -> [1, 4, 2, 5 , 8 ] - Без изменений, поскольку 5 <8
[1, 4, 2 , 5 , 8] -> [1, 4, 2 , 5 , 8] - Без изменений, поскольку 5> 2
[1, 4 , 2 , 5, 8] -> [1, 2 , 4 , 5, 8] - Мы меняем местами 4 и 2, так как 2 <4
[ 1 , 2 , 4, 5, 8] -> [ 1 , 2 , 4, 5, 8] - Без изменений, поскольку 2> 1

Здесь наш массив сортируется за одну итерацию, в отличие от двух итераций пузырьковой сортировки. Коктейльная сортировка сделала это с 7 сравнениями, тогда как пузырьковая сортировка сделала это с 8. Это не так уж много в этом масштабе, хотя с большими числами мы увидим повышение производительности.

Обычно это приводит к увеличению производительности на 33%.

Дональд Э. Кнут упомянул сортировку с помощью коктейльного шейкера и несколько похожих вариантов пузырьковой сортировки в своей знаменитой монографии «Искусство компьютерного программирования» :

Но ни одно из этих усовершенствований не приводит к алгоритму лучше, чем прямая вставка [то есть сортировка вставкой]; и мы уже знаем, что прямая вставка не подходит для больших N. [...]

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

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

Поскольку наш массив содержит n элементов, пузырьковая сортировка выполняет O (n) сравнений n раз. Это приводит нас к общему времени работы O (n ^2^ ) - в среднем и худшем случае. Это ужасная временная сложность для алгоритма сортировки.

Для справки, наиболее распространенные алгоритмы сортировки, такие как Quicksort или Merge Sort, имеют среднее время выполнения O (nlogn) .

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

Используя встроенную console.time() , мы можем сравнить время, необходимое для запуска кода на массивах разной длины:

 console.time('bubble'); 
 bubbleSort(inputArr); 
 console.timeEnd('bubble'); 

Мы сделаем это для массивов размером 100 , 1 000 и 10 000 :

Количество элементов Неоптимизированная пузырьковая сортировка Пузырьковая сортировка с логическим флагом Пузырьковая сортировка с n-k + 1 итерациями Шейкер Сорт 100 2 мс 1 мс 1 мс 1 мс 1000 8 мс 6 мс 1 мс 1 мс 10 000 402 мс 383 мс 2 мс 1 мс

Здесь очевидно, насколько неэффективна первая реализация по сравнению с такими вариантами, как коктейльный шейкер.

Заключение

Хотя пузырьковая сортировка очень интуитивно понятна и проста для понимания и реализации, она крайне непрактична для решения большинства проблем.

Он имеет среднее и худшее время работы O (n ^2^ ) и может работать только с лучшим временем работы O (n), когда массив уже отсортирован.

Его пространственная сложность - O (1) , что очень хорошо . К сожалению, этого недостаточно, чтобы компенсировать ужасную временную сложность.

Даже среди простых алгоритмов сортировки O (n ^2^ ) сортировка вставкой или сортировка по выбору обычно значительно более эффективны.

Из-за своей простоты пузырьковая сортировка часто используется в качестве введения в алгоритмы сортировки на вводных курсах информатики.