PetrTamozhniy Mar 4 2023 at 17:54

Истинная сложность алгоритма Bubble Sort

Easy

3 min

10K

При изучении алгоритмов сортировок, возник вопрос об общепринятой оценке сложности, а так же к примерам реализации. И эти вопросы возникли сразу на первой сортировке Пузырьком. Заговор? Невнимательность? Небрежность? Шутка?

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

Далее на просторах интернета можно встретить разные реализации данной сортировки, например (JS):

function BubbleSort(array)
{
  for(i = 0; i < array.length; i++)
  {
    for(j = 0; j < array.length - 1; j++)
    {
      if(array[j] > array[j + 1])
      {
        var temp = array[j]
        array[j] = array[j + 1]
        array[j + 1] = temp
      }
    }
  }
}

И тут возникают несостыковки:

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

Если покопаться в других примерах, или немного подумать логически то это решается следующим примером (и снова JS):

function BubbleSort2(array)
{
  var result = [...array] //Делаем копию массива, чтобы не мутировать данные
  var isSorted = false //Утверждение что массив не отсортирован
  var temp /*Переменная для операции обмена, 
            вынесена сюда чтобы сразу зарезервировать ячеку памяти, 
            а не создавать каждый раз при операции обмена*/

  function Swap(a, b) //Вынесли операцию обмена в отдельную функцию
  {
    temp = result[a]
    result[a] = result[b]
    result[b] = temp
  } 
  /*Можно сделать и без 3ей переменной, но думаю это избыточно, 
    т.к. памяти много не занимает*/
    
  for(i = 0; i < result.length && !isSorted; i++) //Цикл прервется если массив отсортирован
  {
    isSorted = true //Вначале каждой итерации утверждаем что массив отсортирован
    for(j = 0; j < result.length - (1 + i); j++) //Уменьшаем с каждой новой итерацией
    {
      if(result[j] > result[j + 1])
      {
        Swap(j, j+1)
        isSorted = false /*Если была произведена операция обмена, 
                           значит массив еще не отсортирован*/
      }
    }
  }

  return result
}

Теперь реализация подходит под условия сортировки и достаточно логична, но есть одно НО!. Если добавить счетчик количества проходов по массиву, то получится следующая картина (возьмём наихудший сценарий, массив из 5ти элементов отсортированный в обратном порядке):

Подсчет количества произведенных действий

Как видно из изображения выше, последняя итерация лишняя, поэтому для первого цикла for можно взять длину (N - 1), но это совершенно не критично.
Но вот то что счетчик показал 15 вместо положенных худшему сценарию , уже странно, куда делось еще 10 операций. Или возможно все таки сложность другая? Но какая?

Ответ: Сложность сортировки пузырьком в худшем сценарии НЕ квадратичная, а равна сумме арифметической прогрессии с разностью в единицу, или или

Под a1 и an следует понимать не само значение, а порядковый номер

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

Но все же странно, что в такой сфере, где бывают возникают споры и из-за более мелких причин, вдруг так пренебрежительно оценивают алгоритм, хотя на выходе мы получаем разницу практически в 2 раза! Например если элементов 100, то фактически 5050 против 10000, а это почти 50%.

И стоит ли говорить о том, что если у сортировки пузырьком не квадратическая сложность, то и у остальных (нормальных квадратических сортировок) тем более.

Вывод

У сортировки пузырьком сложность , но это не делает её быстрее, это по прежнему медленная сортировка. Однако если Ваш алгоритм действительно имеет сложность , то это практически в 2 раза хуже чем алгоритм Bubble Sort в худшем сценарии!

Tags:

Hubs:

Algorithms