Сравнение алгоритма быстрой сортировки

Question

Не могу понять, почему мой алгоритм сортировки падает на массив с 50000 числами

const myquicksort2 = (sortedArray) => {

    const sort = (start, end) => {
        if (end - start <= 1) return;
        let pivot = sortedArray[end - 1];
        let pivotIndex = end - 1;

        for (let i = start; i < end; i++) {
            if (sortedArray[i] > pivot && i < pivotIndex) {
                let temp = sortedArray[i];
                sortedArray[i] = pivot;
                sortedArray[pivotIndex] = temp;
                pivot = temp;
            }
        }
        sort(start, pivotIndex);
        sort(pivotIndex + 1, end);
    };

    sort(0, sortedArray.length);

    return sortedArray;
};

Я не создаю новые массивы и не меняю сводное значение при сортировке, но во втором примере не происходит сбой50000 и работает намного лучше на https://jsperf.com/sorting12389

function sort(arr) {
   if (arr.length > 1) {
     const medium = arr[0];
     const leftPart = [];
     const centerPart = [];
     const rightPart = [];

     arr.forEach((item) => {
       if (item < medium) leftPart.push(item);
       if (item > medium) rightPart.push(item);
       if (item === medium) centerPart.push(item);
     })

     return sort(leftPart).concat(centerPart).concat(sort(rightPart));
   } else {
     return arr;
   }
 }

Answer 1

Здесь есть пара проблем.

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

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

sort(pivotIndex + 1, end)

Чтобы заставить работать быструю сортировку на месте, вам нужна схема разбиения, которая сбрасывает индекс сводной оси,затем вы повторно используете start - pivot и pivot+1 - end.

Распространенная схема разбиения - это разделение Hoare, где вы перемещаете две переменные с противоположных сторон массива, меняя местами, когда вы находите значения по обе стороны от оси.Это не сложно, но легко испортить индексы.

Раздел обычно пишется как отдельная функция, но чтобы сохранить его близким к вашему, я просто выделил его:

const myquicksort2 = (sortedArray) => {
  const sort = (start, end) => {    
      if (end <= start) return;
      let pivot = sortedArray[end];
      let left = start, right = end
     
      // Partion 
      while(left <= right){
        while (sortedArray[left] < pivot){ 
          left++ 
        }     
        while (sortedArray[right] > pivot){ 
          right-- 
        }
        if (left <= right) {
          [sortedArray[left], sortedArray[right]] = [sortedArray[right], sortedArray[left]]
          left++
          right--
        }
      }

      sort(start, right);
      sort(right + 1, end);
  };

  sort(0, sortedArray.length-1);

  return sortedArray;
};

console.log(myquicksort2([5, 7, 2, 1, 11, 10]))

Когда я запускаю это с временными тестами в Node, это значительно быстрее, чем функция, которая создает массивы.В вашем jsperf это не так.Однако, если я создаю новый массив с каждым циклом, это скорее говорит о том, что в том, как работает jsperf, есть что-то, чего мы не видим.Вот редактирование jsperf

На моем ноутбуке с узлом, сортирующим 100 000 случайных целых чисел за 20 мс, функция не на месте занимает около 50 мс.