LogoData Structures & Algorithms

Быстрая сортировка (Quicksort)

Алгоритм сортировки, который использует принцип "разделяй и властвуй". Для этого он рекурсивно делит массив на две части, выбирая опорный элемент pivot. Затем все элементы меньше опорного перемещаются в один подмассив, а все элементы больше – в другой. Затем рекурсивно сортируются левый и правый подмассивы и объединяются: [quickSort(left), equal, quickSort(right)].
Сложность:

Время – O(n log n) в среднем, O(n^2) в худшем; Память – O(n) для результата + стек O(log n) в среднем.

quicksort.ts
1function quicksort(arr: number[]): number[] {
2    if (arr.length <= 1) {
3        return arr.slice();
4    }
5    const pivot = arr[Math.floor(arr.length / 2)]; // pivot - опорный элемент
6    const less = [];
7    const equal = [];
8    const greater = [];
9    for (const i of arr) {
10        if (i < pivot) less.push(i);
11        else if (i > pivot) greater.push(i);
12        else equal.push(i);
13    }
14    return [...quicksort(less), ...equal, ...quicksort(greater)];
15}
16

17quicksort([10,5,2,3]) // -> [2,3,5,10]
18quicksort([10,-2,7,7,0,4]) // -> [-2,0,4,7,7,10]
19quicksort([]) // -> []
20quicksort([1]) // -> [1]
21