O(log2n*n)
самый быстрый
разделяй и властвуй
делим массив на подмассивы и каждый раз рекурсивно
мы выбираем опорный элемент у каждого массива
его можно выбрать случайно, но часто центрально
пробегаемся по массиву и все элементы, которые меньше опорного, добавляем в один массив, все которые больше, добавляем в другой массив.
После такой операции у нас получается два массива
(с меньшими числами и с большими числами чем опорные).
Для каждого из этих массивов выполняется точно такая же операция. В каждой из этих массивов выбирается опорный элемент и происходит сортировка и так происходит до тех пор, пока длина массива становится равна единице (именно это условие и будет базовым случаем выхода из рекурсии).
И после этих операций эти маленькие массивы склеиваются в один большой.
const arr=[1,4,5,8,51,2,7,5,5,2,11]//[0,1,1,2,3....]
let cnt=0;
function quickSort(arr){
if (arr.length<=1){
return arr
}
let pivotIndex = Math.floor(arr.length/2);
let pivot=arr[pivotIndex]
let less=[]
let greater=[]
for(let i=0;i<arr.length;i++){
cnt+=1
if(i===pivotIndex)
continue;
if(arr[i]<pivot){
less.push(arr[i])
} else {
greater.push(arr[i])
}
return [...quickSort(less),pivot,...quickSort(greater)]
}
console.log(quickSort(arr))
console.log(cnt);
