Что такое метод пузырьковой сортировки?
Не самый эффективный метод с точки зрения временной сложности, но его можно оптимизировать. В двух словах, метод пузырьковой сортировки берет массив смежных элементов и сравнивает их друг с другом. Если по какой-либо причине элементы не идут в порядке возрастания, элемент будет заменен.
Как это работает
Мы можем взять пример массива [4,6,1,7,3,2,5]. Мы можем начать с итерации по массиву.
for(let i = array.length - 1; i > 0; i--)
Обратите внимание, что мы начинаем уменьшать, а не увеличивать массив. Это потому, что мы хотим уменьшать значение при каждом просмотре элемента.
Как только первая итерация установлена, мы можем начать наш второй набор итераций. Нам не нужно уменьшаться. Мы можем увеличивать каждый элемент следующим образом.
for(let j = 0; j < array.length; j++)
Теперь пришло время установить наш условный оператор. Наша основная цель — поменять местами, если текущий элемент больше следующего.
if(array[j] > array[j + 1])
Кроме того, мы обмениваем наши предметы. И вернуть массив. Вот полное решение ниже.
function bubbleSort(array){
for(let i = array.length - 1; i > 0; i--){
for(let j = 0; j < array.length; j++){
if(array[j] > array[j + 1]){
//swap and return array
let temp = array[j]
array[j] = array[j + 1]
array[j + 1] = temp
}
}
}
return array
}
//result [1, 2, 3, 4, 5, 6, 7]
Какова временная сложность?
Учитывая тот факт, что нам пришлось вдвое увеличить временную сложность для этой техники, она работает за O(n)², что делает ее наихудшим сценарием. Однако его можно оптимизировать.
