Quick Sort

Core idea

Quick Sort chooses a pivot element and rearranges the array so that smaller values go to the left and larger values go to the right.

After partitioning, it repeats the same process recursively for both halves, which makes the algorithm dramatically faster than Bubble Sort on average.

It is one of the classic divide-and-conquer algorithms: elegant, fast in practice, and useful for understanding recursion and partitioning.

// Выбираем опорный элемент и делим массив на 2 части,
// первая часть - это элементы меньше опорного, вторая - больше опорного
// лучший случай O(n*log(n))
// O(n^2)

function quickSort (arr) {
 if (arr.length <= 1) {
   return arr;
 }

 const pivot = arr[arr.length - 1];
 const left = [];
 const right = [];

 for (let i = 0; i < arr.length - 1; i++) {
   if (arr[i] < pivot) {
     left.push(arr[i]);
   } else {
     right.push(arr[i]);
   }
 }

 return [...quickSort(left), pivot, ...quickSort(right)];
}