Алгоритмы сортировки. Bubble Sort

Наверное, самый известный алгоритм сортировки — пузырьковая сортировка. Примечательно тем, что от нее есть тысячи мутаций, и в основном используется она только в учебных целях — как первый алгоритм которые вы выучите.

Итак, что такое пузырьковая сортировка? Представьте что мы берем два первых элемента. Если первый элемент больше второго — меняем их местами. Теперь берем второй и третий элемент — повторяем. Таким образом, в конце концов — самый большой элемент окажется последним членом массива. Теперь, повторяем операцию для n-1 первых чисел, потому n-2, и так далее.

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

Код невероятно прост:

var bubble_sort_classic = function(array){
  var length = array.length;
  for (var i = 0; i < length; i++){
    for ( var j = 0; j < length — i — 1; j++){
      if (array[j] > array[j + 1] ){
        array.swap(j, j + 1);
      } 
    }
  }
  return array;
};

Честно говоря, картинка не показывает точную работу алгоритма, как вы уже заметили она начинает с конца, но суть остается та же.

Я не перепутал цифры — он действительно так медленно работает☺

Мы можем совсем чуть оптимизивароть наш алгоритм, чтобы быть уверенными, что он, в случае уже отсортированного массива не будет пробегать массив еще раз ( а то и неколько ):

var bubble_sort = function(array){
  var length = array.length;
  var swapped = false;
  for (var i = 0; i < length; i++){
    swapped = false;
    for ( var j = 0; j < length — i — 1; j++){
      if (array[j] > array[j + 1] ){
        array.swap(j, j + 1);
        swapped = true;
      } 
    }
 if (!swapped){
      break;
    }
 }
 return array;
};

Собственно, единственное что мы сделали — добавили переменную swapped которая отмечает, или пройдя массив — мы делали перестановку элементов. Если нет — то массив отсортирован, и мы можем заканчивать☺Честно говоря, на генеренных массивах — выигрыша нет, а даже проигрыш.

Исходники примеров вы можете найти тут.