Реализация Quicksort “быстрой сортировки” в JavaScript

Эта статья расскажет о реализации быстрой сортировки в JavaScript. Быстрая сортировка не встроена в JavaScript. Из-за метода сортировки в прототипе Array сортировка редко подвергается сомнению или оптимизируется в языке. Несмотря на это, Quicksort по-прежнему является важным алгоритмом, по крайней мере, для понимания, используете ли вы его или нет.

Как это работает?

Quicksort работает, выбирая элемент из массива и обозначая его как «pivot». Все остальные элементы в массиве делятся на две категории - они меньше или больше, чем этот элемент сводки.

Каждый из двух результирующих массивов (массив значений, меньших, чем pivot, и массив значений, превышающих pivot), затем обрабатывается по тому же алгоритму. Опорная точка выбрана, и все остальные значения разделены на два массива значений меньше и больше.

В конце концов, подмассив будет содержать одно значение или не иметь значения вообще, так как больше не будет значений, с которыми его можно сравнивать. Все остальные значения были обозначены как «pivot» в некоторой предыдущей точке и не опускались до этого нижнего подмассива. В этот момент значения будут отсортированы, поскольку все значения теперь объявлены как меньшие или большие, чем все другие значения в массиве.

Как мы это реализуем?

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

const quickSort = (unsortedArray) => {
  const sortedArray = TODO(unsortedArray);
  return sortedArray;
};

Поскольку «значение» элемента в массиве может быть неочевидным, мы должны предложить необязательный параметр для алгоритма сортировки. Сортировка строк или чисел встроена в JavaScript, но сортировка объектов - нет. Мы можем отсортировать коллекцию пользовательских объектов ({name: 'Charles', age: 21}) по возрасту.

const defaultSortingAlgorithm = (a, b) => {
  if (a < b) {
    return -1;
  }
  if (a > b) {
    return 1;
  }
  return 0;
};

const quickSort = (
  unsortedArray,
  sortingAlgorithm = defaultSortingAlgorithm
) => {
  const sortedArray = TODO(unsortedArray);
  return sortedArray;
};

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

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

Массив перед шарниром делится на две части: меньше, чем шарнир спереди, больше, чем шарнир на конце. Наконец, сама сводная точка перемещается между двумя вложенными массивами, а затем сортируются по одному и тому же алгоритму быстрой сортировки.

const quickSort = (
  unsortedArray,
  sortingAlgorithm = defaultSortingAlgorithm
) => {

  const sortedArray = [...unsortedArray];
  const recursiveSort = (start, end) => {

    if (end - start < 2) {
      return;
    }
    const pivotValue = sortedArray[end];
    let splitIndex = start;
  };

  recursiveSort(0, unsortedArray.length - 1);
  return sortedArray;
};

Мы создаем sortedArray как новый массив, чтобы не изменять исходный массив. Это не обязательно, но это хорошая практика.

Мы создаем recursiveSort как рекурсивную функцию, которая будет принимать подмассив (от начального индекса до конечного индекса) и быстро сортировать его, мутируя по пути sortedArray. Весь массив - это первый массив, который будет передан этой рекурсивной функции.

Наконец, отсортированный массив возвращается.

Функция recursiveSort имеет переменную pivotValue для обозначения значения нашего центра и переменную splitIndex для обозначения индекса, ограничивающего массивы меньше и больше чем. Концептуально, все значения меньше чем будут с индексами меньше, чем splitIndex, и все значения больше чем будут с индексами больше, чем splitIndex. splitIndex инициализируется в начале подмассива, но когда мы обнаружим значения, меньшие, чем значение pivot, мы соответствующим образом настроим splitIndex.

Мы перебрать все значения без поворота, перемещения те меньше, чем значение поворота, чтобы перед указателем начала.

const quickSort = (
  unsortedArray,
  sortingAlgorithm = defaultSortingAlgorithm
) => {

  const sortedArray = [ ...unsortedArray ];
  const recursiveSort = (start, end) => {

    if (end - start < 2) {
      return;
    }

    const pivotValue = sortedArray[end];
    let splitIndex = start;
    for (let i = start; i < end; i++) {
      const sort = sortingAlgorithm(sortedArray[i], pivotValue);

      if (sort === -1) {

        if (splitIndex !== i) {
          const temp = sortedArray[splitIndex];
          sortedArray[splitIndex] = sortedArray[i];
          sortedArray[i] = temp;
        }

        splitIndex++;
      }

    }

    sortedArray[end] = sortedArray[splitIndex];
    sortedArray[splitIndex] = pivotValue;

    recursiveSort(start, splitIndex - 1);
    recursiveSort(splitIndex + 1, end);
  };

  recursiveSort(0, unsortedArray.length - 1);
  return sortedArray;
};

Мы перемещаем все значения, меньшие, чем значение pivot, в splitIndex, и все оставляем все остальные значения там, где они есть (по умолчанию больше, чем splitIndex, поскольку индекс разделения начинается в начале подмассива).

После переупорядочения под-массива мы перемещаем саму ось в разделение, поскольку знаем, что она расположена между всеми значениями меньше или больше или равно.