Шаг 1

Реализация быстрой сортировки сложнее сортировки пузырьком, однако ничего страшного в ней нет. Напоминаем, что нам предстоит написать несколько вещей: 1. Разделение массива на точке поворота. 2. Перемещение элементов больше неё направо, меньше — налево. 3. Вызов сортировки на каждой из этих частей.

/*
quickSort([5, 3, 2, 1]) => [1, 2, 3, 5]
quickSort([1, 2, 3]) => [1, 2, 3]
*/

function quickSort(array) {
  return array;
}

Шаг 2

Начнём с первой части нашего алгоритма — функции, которая будет «раскидывать» элементы вокруг поворотной точки. Её мы будем выбирать в нашем массиве случайным образом. Сначала напишем функцию-хелпер, которая поможет нам искать индекс этой точки.

/*
quickSort([5, 3, 2, 1]) => [1, 2, 3, 5]
quickSort([1, 2, 3]) => [1, 2, 3]
*/

function quickSort(array) {
  return array;
}

function random(min, max) {
    const interval = max - min; // Интервал, в котором могут находится наши числа
    const shift = min; // Поиск рандомного числа будет начинаться не с нуля, а с min

    return Math.round(Math.random() * interval + shift);
}

Шаг 3

Теперь можно написать и «функцию-раскидыватель». Рассказать принцип её работы проще по уже готовому коду, так что обратите внимание на комментарии к ней!

/*
quickSort([5, 3, 2, 1]) => [1, 2, 3, 5]
quickSort([1, 2, 3]) => [1, 2, 3]
*/

function quickSort(array) {
  return array;
}

function random(min, max) {
    const interval = max - min; // Интервал, в котором могут находится наши числа
    const shift = min; // Поиск рандомного числа будет начинаться не с нуля, а с min

    return Math.round(Math.random() * interval + shift);
}

// Так как в подразбиениях после рекурсивного вызова сортировки мы будем работать не с целым массивом а его частями, сразу сделаем дополнительные параметры для их определения
function partition(array, left, right) {
  // Находим значение, вокруг которого будем размещать элементы
  const pivot = array[random(left, right)];

  // как и в бинпоиске, будем сходиться с краев в центр, пока не просмотрим все элементы
  while (left < right) {
    // Пока слева встречаются только числа меньше поворотного...
    while (array[left] < pivot) {
        // ... просто двигаем левый указатель вправо, ведь с этими числами ничего делать не надо
        left++;
    }

    // Пока справа встречаются только числа больше поворотного...
    while (array[right] > pivot) {
      // ... просто двигаем правый указатель влево, ведь с этими числами ничего делать не надо
      right--;
    }

    // А как только оба указателя показывают на элементы, которые должны быть в противоположных частях И мы всё ещё не сошлись к центру...
    if (left <= right) {
        // ...меняем их местами и не забываем двигать оба указателя, так как теперь оба числа на своём месте
        [array[left], array[right]] = [array[right], array[left]];
        left++;
        right--;
    }
  }

  // Возвращаем место, где оказался элемент, равный нашей точке поворота
  return left;
}

Шаг 4

Осталось дописать непосредственно сортировку. Напомним, что нам нужно лишь вызывать разбиение массива и эту же сортировку на каждом из разбиений, пока мы не «спустимся» к разбиениям из одного элемента. Кстати, в движке V8, который запускает JavaScript внутри Chrome, подобная реализация сортировки используется в Array.prototype.sort() для сортировки массивов из 23 и более элементов. Для меньших разбиения и рекурсия — слишком долго, поэтому для них используется сортировка вставкой, о которой мы узнаем в следующей главе!

import {logIteration} from "./logger";

/*
quickSort([5, 3, 2, 1]) => [1, 2, 3, 5]
quickSort([1, 2, 3]) => [1, 2, 3]
*/

// Тут нам тоже нужно определить дополнительные параметры, как и в разбиении, чтобы нормально работать с подмассивами
function quickSort(array, left, right) {
  // если мы работаем с целым массивом и нам не передали края сортировки, определим их сами
  left = left ?? 0;
  right = right ?? array.length - 1;

  // разбиваем наш массив на подмассивы вокруг точки поворота
  const pivotIndex = partition(array, left, right);
  logIteration(array, array[pivotIndex], left, right);

  // если в левом подмассиве больше одного элемента, то сортируем его
  if (left < pivotIndex - 1) {
    quickSort(array, left, pivotIndex - 1);
  }

  // то же и с правым
  if (pivotIndex < right) {
    quickSort(array, pivotIndex, right);
  }

  return array;
}

function random(min, max) {
    const interval = max - min; // Интервал, в котором могут находится наши числа
    const shift = min; // Поиск рандомного числа будет начинаться не с нуля, а с min

    return Math.round(Math.random() * interval + shift);
}

// Так как в подразбиениях после рекурсивного вызова сортировки мы будем работать не с целым массивом а его частями, сразу сделаем дополнительные параметры для их определения
function partition(array, left, right) {
  // Находим значение, вокруг которого будем размещать элементы
  const pivot = array[random(left, right)];

  // как и в бинпоиске, будем сходиться с краев в центр, пока не просмотрим все элементы
  while (left < right) {
    // Пока слева встречаются только числа меньше поворотного...
    while (array[left] < pivot) {
        // ... просто двигаем левый указатель вправо, ведь с этими числами ничего делать не надо
        left++;
    }

    // Пока справа встречаются только числа больше поворотного...
    while (array[right] > pivot) {
      // ... просто двигаем правый указатель влево, ведь с этими числами ничего делать не надо
      right--;
    }

    // А как только оба указателя показывают на элементы, которые должны быть в противоположных частях И мы всё ещё не сошлись к центру...
    if (left <= right) {
        // ...меняем их местами и не забываем двигать оба указателя, так как теперь оба числа на своём месте
        [array[left], array[right]] = [array[right], array[left]];
        left++;
        right--;
    }
  }

  // Возвращаем место, где оказался элемент, равный нашей точке поворота
  return left;
}

quickSort([56, 87, 18, 92, 42, 31, 44, 82, 36, 91]);

File logger

const results = document.getElementById('results')

export function logIteration(array, pivot, start, end) {
  const result = document.createElement('li');

  result.innerHTML = `[${array.join(', ')}], разделение вокруг ${pivot}, с ${start} по ${end} индексы`;

  results.appendChild(result);
}
de>