Quicksort
- Эффективный алгоритм сортировки для больших наборов данных, где он работает быстрее, чем сортировка слияния и сортировка кучи.
- Разработан британским компьютерным ученым Тони Хоаре в 1959 году и опубликован в 1961 году.
Как работает quicksort?
Массив состоит из 5 предметов [3, 6, 4, 1, 2]
1). Во-первых, нам нужно выбрать значение pivot из массива, мы можем выбрать какое угодно значения в качестве pivot, мы выбираем последний элемент 2 в качестве pivot.
2). Затем нам нужно пройти через массив и сравнить с pivot, если какой-либо элемент, будет меньше, чем pivot, разместим на левой стороне, иначе, если какой-либо элемент больше, чем pivot, разместим на правой стороне.
[ 3, 6, 4, 1, 2] pivot = 2 left = [1] right = [3, 6, 4]
Нам нужно запустить quickSort рекурсивно для правой части и левой части
[ 3, 6, 4, 1, 2] pivot = 2 left = [1] right = [3, 6, 4] left = [1] right = [3, 6, 4] pivot = 4; left [3] right = [6] right =[3] + pivot + [6] = [3, 4, 6] Финальная сортировка массива [1] + pivot + [3, 4, 6] = [1, 2, 3, 4, 6]
Алгоритм быстрой сортировки
Давайте реализуем алгоритм быстрой сортировки.
Во-первых, мы создаем функцию с тремя параметрами, которыми являются arr, length и start.
arr: неотсортированный массив
lenght: сколько раз нам нужно делать цикл, наше значение pivot — это последний элемент массива, так что наш цикл заканчивается перед поворотом значения.
start: цикл начинается с 0.
function quickSort(arr,length = arr.length-1,start=0){
if(arr.length < 2) return arr const pivot = arr[arr.length-1]; const left = [ ]; const right = [ ]; }
Затем мы используем цикл while, который помогает нам перебирать элементы в несортированном массиве, и если какой-либо элемент меньше значения pivot, перемещается в левый массив, а затем вставляем в правый массив.
function quickSort(arr,length = arr.length-1,start=0){
if(arr.length < 2) return arr
const pivot = arr[arr.length-1];
const left = [ ];
const right = [ ];
while (start < length) {
if (arr[start] < pivot) left.push(arr[start])
else right.push(arr[start])
start++
}
}
На последнем этапе нам нужно запустить quickSort рекурсивно как с левой, так и с правой стороны.
function quickSort(arr, length = arr.length - 1, start = 0) {
if (arr.length < 2) return arr // базовый вариант
const pivot = arr[arr.length - 1]; // Значение pivot
const left = [ ];
const right = [ ];
while (start < length) {
if (arr[start] < pivot) left.push(arr[start])
else right.push(arr[start])
start++
}
return [...quickSort(left), pivot, ...quickSort(right)];
}
console.log(quickSort([4, 9, 2, 6, 8, 10, 3, 1, 7, 5])) // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]