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

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

Вступление

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

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

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

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

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

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

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

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

Визуализация пузырьковой сортировкиgif{.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^ ) сортировка вставкой или сортировка по выбору обычно значительно более эффективны.

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

comments powered by Disqus