Алгоритм быстрой сортировки (QuickSort) на JavaScript

QuickSort – это рекурсивный алгоритм сортировки массива. Он использует “разделяй и властвуй” стратегию для сортировки элементов. Алгоритм работает так:

1. Выбирается “опорный” элемент (обычно первый элемент массива).
2. Остальные элементы массива разделяются на две части: меньшие и большие, чем опорный элемент.
3. Шаги 1 и 2 повторяются рекурсивно для каждой части до тех пор, пока не будет достигнута единственная ячейка.
4. Результаты из каждой рекурсии соединяются вместе в один отсортированный массив.

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

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

Пример кода QuickSort на JavaScript:

function quickSort(array, left, right) {
  let pivot;
  let partitionIndex;
  
  if (left < right) {
    pivot = right;
    partitionIndex = partition(array, pivot, left, right);
    
    //sort left and right
    quickSort(array, left, partitionIndex - 1);
    quickSort(array, partitionIndex + 1, right);
  }
  return array;
}

function partition(array, pivot, left, right) {
  let pivotValue = array[pivot];
  let partitionIndex = left;
  
  for (let i = left; i < right; i++) {
    if (array[i] < pivotValue) {
      swap(array, i, partitionIndex);
      partitionIndex++;
    }
  }
  swap(array, right, partitionIndex);
  return partitionIndex;
}

function swap(array, i, j) {
  let temp = array[i];
  array[i] = array[j];
  array[j] = temp;
}

В этом примере функция quickSort вызывается рекурсивно, пока не будет достигнута единственная ячейка. Функция partition выполняет разделение элементов массива на две части, а функция swap меняет местами два элемента в массиве.

Давайте более подробном рассмотрим каждую часть кода.

function quickSort(array, left, right) {
  let pivot;
  let partitionIndex;
  
  if (left < right) {
    pivot = right;
    partitionIndex = partition(array, pivot, left, right);
    
    //sort left and right
    quickSort(array, left, partitionIndex - 1);
    quickSort(array, partitionIndex + 1, right);
  }
  return array;
}

• quickSort это основная функция сортировки QuickSort.
• left и right задают границы текущего участка массива, который мы сортируем.
• pivot выбирает последний элемент массива в качестве опорного.
• partitionIndex – это переменная, которая хранит индекс элемента, который будет разделять массив на две части.
• Если left < right, это означает, что участок массива содержит более одного элемента, и мы можем продолжать.
• partitionIndex вычисляется с помощью функции partition.
• После того, как partitionIndex вычислен, мы рекурсивно вызываем quickSort для левой и правой частей массива.
• В конечном итоге, когда участок массива содержит только один элемент, функция возвращает отсортированный массив.

function partition(array, pivot, left, right) {
  let pivotValue = array[pivot];
  let partitionIndex = left;
  
  for (let i = left; i < right; i++) {
    if (array[i] < pivotValue) {
      swap(array, i, partitionIndex);
      partitionIndex++;
    }
  }
  swap(array, right, partitionIndex);
  return partitionIndex;
}

• partition это функция, которая определяет, как мы разделяем массив на две части.
• pivot – это индекс опорного элемента.
• left и right – это границы участка массива, который мы разделяем.
• pivotValue – это значение опорного элемента.
• partitionIndex – это индекс, который будет разделять массив на две части. Он начинается с left.
• Цикл for идет от left до right – 1, т.е. до предпоследнего элемента.
• Если текущий элемент array[i] меньше pivotValue, мы меняем его местами с array[partitionIndex] с помощью функции swap.
• Затем мы увеличиваем partitionIndex на 1.
• После завершения цикла, мы меняем местами array[right] и array[partitionIndex].
• Функция возвращает partitionIndex.

QuickSort является одним из самых популярных и эффективных алгоритмов сортировки. Некоторые похожие алгоритмы:

• Merge Sort
• Heap Sort
• Bubble Sort
• Insertion Sort
• Selection Sort

Все эти алгоритмы относятся к категории сортировок сравнением, так как они работают с сравнением элементов между собой. Однако, QuickSort является одним из самых быстрых из этих алгоритмов, в зависимости от подхода к выбору опорного элемента.