Быстрая сортировка — проект на JavaScript

JS.20 · Алгоритмы

Задача

Отсортировать массив методом «разделяй и властвуй».

Алгоритм

Опорным берётся первый элемент, остальные делятся на меньшие и большие через filter и сортируются рекурсивно.

Исходный код

// Быстрая сортировка
const quickSort = a => {
  if (a.length <= 1) return a;
  const [p, ...rest] = a;
  const less = rest.filter(x => x < p);
  const more = rest.filter(x => x >= p);
  return [...quickSort(less), p, ...quickSort(more)];
};

console.log(quickSort([5, 2, 9, 1, 7, 3, 8, 4, 6, 0]));

Пояснения

Наглядно, но filter создаёт новые массивы; на больших данных in-place вариант экономнее.