-
Notifications
You must be signed in to change notification settings - Fork 28
/
5_quick_sort.js
46 lines (40 loc) · 2.31 KB
/
5_quick_sort.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// Быстрая сортировка(Quick Sort)
// Один из самых эффективных алгоритмов
const arr = [
0, 3, 2, 5, 6, 8, 23, 9, 4, 2, 1, 2, 9, 6, 4, 1, 7, -1, -5, 23, 6, 2, 35, 6,
3, 32, 9, 4, 2, 1, 2, 9, 6, 4, 1, 7, -1, -5, 23, 9, 4, 2, 1, 2, 9, 6, 4, 1, 7,
-1, -5, 23,
];
let count = 0;
// Суть: Работает по принципу "Разделяй и властвуй". Мы делим массив на подмассивы и каждый раз рекурсивно.
// Выбираем опорный элемент у каждого массива(его можно выбрать случайно, но чаще всего берут центральный).
// Пробегаемся по массиву и все элементы, которые по значению меньше опорного - добавляем в один массив,
// а все которые больше - в другой. И для каждого из этих массивов выполняется такая же операция.
// Так делается до тех пор, пока длина массива не станет равна 1.
function quickSort(array) {
if (array.length <= 1) {
return array;
}
// pivotIndex - опорный индекс элемента, в нашем случае берем центральный (array.length / 2)
let pivotIndex = Math.floor(array.length / 2);
// pivot - сам опорный элемент, в нашем случае берем центральный
let pivot = array[pivotIndex];
// массив с числами, которые меньше чем опорные
let less = [];
// массив с числами, которые больше чем опорные
let greater = [];
// Проходимся по всему массиву и наполняем массивы less и greater
for (let i = 0; i < array.length; i++) {
count += 1;
if (i === pivotIndex) continue;
if (array[i] < pivot) {
less.push(array[i]);
} else {
greater.push(array[i]);
}
}
// Проделывем ту же самую операцию с двумя след. массивами
return [...quickSort(less), pivot, ...quickSort(greater)];
}
console.log(quickSort(arr));
console.log("count", count);