С тех пор, как я впервые услышал об алгоритмах сортировки, они всегда были синонимом большого удовольствия!

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

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

  • сортировка вставками;
  • пузырьковая сортировка;
  • Сортировка слиянием;
  • Быстрая сортировка.

Надеюсь, что эта статья поможет вам прояснить их концепцию и предоставить вам простую реализацию.

Сортировка вставками

function insertionSort(arrayToSort) { 
  for (let i = 1; i < arrayToSort.length; i++) {  
    let j = i;  
    while (j > 0 && arrayToSort[j-1] > arrayToSort[j]) {   
      swap(arrayToSort, j-1, j);
      j--;   
    } 
  } 
  return arrayToSort;
}

Сортировка вставками работает, беря элементы из списка один за другим, а затем сравнивая значения со значениями, уже посещенными в текущем списке. К концу n итераций мы гарантируем, что n элементы отсортированы.

* В худшем случае O(n^{2}) сравнений
* В лучшем случае O(n) сравнений

Пузырьковая сортировка

function bubbleSort(arrayToSort) {
  for (let i = 0; i < arrayToSort.length; i++) {
    for (let j = 0; j < (arrayToSort.length - i - 1); j++) {
      if (arrayToSort[j] > arrayToSort[j+1]) {
        swap(arrayToSort, j, j+1);
      }
    }   
  }
  return arrayToSort;
}

Пузырьковая сортировка довольно проста и неэффективна. Эффективность будет зависеть от списка, заданного в качестве входных данных, но в большинстве случаев эффективен только при использовании в почти отсортированном/отсортированном списке.

* В худшем случае O(n^{2}) сравнений
* В лучшем случае O(n^{2}) сравнений — может быть O(n), если добавить дополнительную проверку, чтобы убедиться, что массив уже отсортирован

Сортировка слиянием

function mergeSort(arrayToSort) {
  if (arrayToSort.length === 1) {
    return arrayToSort;
  }
  const middle = Math.floor(arrayToSort.length / 2);
  const left = arrayToSort.slice(0, middle); 
  const right = arrayToSort.slice(middle);
  return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
  let result = [];
  while (left.length && right.length) {
    if (left[0] > right[0]) {
      result.push(right.shift());
    } else {
      result.push(left.shift());
    }
  }
  while (left.length) {
    result.push(left.shift());
  }
  while (right.length){
    result.push(right.shift());
  }
  return result;
}

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

* В худшем случае O(n log n) сравнений
* В лучшем случае O(n log n) сравнений

Быстрая сортировка

function quickSort(arrayToSort) {
  if (arrayToSort.length <= 1) {
    return arrayToSort;
  }
  let left = [];
  let right = [];
  let result = [];
  let pivot = arrayToSort.shift();
  
  for (let i=0; i < arrayToSort.length; i++) {
    if (arrayToSort[i] > pivot) {
      right.push(arrayToSort[i]);
    } else {
      left.push(arrayToSort[i]);
    }
  }
  return result.concat(quickSort(left), pivot, quickSort(right));
}

Быстрая сортировка отлично подходит для больших списков. Использует подход «разделяй и властвуй». Алгоритм выбирает опорную точку и из этой опорной точки список разбивается на более мелкие списки. Имейте в виду, что выбор хорошего разворота (разворот должен быть как можно ближе к медиане, в текущей реализации я выбираю первый элемент) может значительно повысить эффективность. Выполнение этого алгоритма может быть легко распределено с использованием многопоточного подхода.

* В худшем случае O(n log n) сравнений
* В лучшем случае O(n log n) сравнений

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

function swap(arrayToSwap, firstIndex, secondIndex) {
  const temp = arrayToSwap[firstIndex];
  arrayToSwap[firstIndex] = arrayToSwap[secondIndex];
  arrayToSwap[secondIndex] = temp;
}

Существует много дополнительной информации об алгоритмах сортировки, не стесняйтесь исследовать. Я также создал общедоступный репозиторий GitHub с этим кодом:
https://github.com/JMGomes/SortingAlgorithms/

В этом репозитории вы обнаружите, что я заменил обычный оператор сравнения (значение1 › значение2) абстрактной функцией с именем customCompare(). Это позволяет пользователям использовать более сложный оператор сравнения, например. чтение свойства объекта.

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

Спасибо