Дороги судьбы, как правило, просёлочные (Авессалом Подводный).

Внедрение алгоритма Quicksort

2 мин для чтения
FavoriteLoadingДобавить в избранное
1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (1 оценок, среднее: 5,00 из 5)
Загрузка...
17 ноября 2018

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]

Если вы нашли ошибку, пожалуйста, выделите фрагмент текста и нажмите Ctrl+Enter.

Просмотров: 17

Если статья понравилась, то поделитесь ей в социальных сетях:

Добавить комментарий

Войти с помощью: 

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Сообщить об опечатке

Текст, который будет отправлен нашим редакторам:

Заполните форму и наш менеджер перезвонит Вам в самое ближайшее время!

badge
Обратный звонок 1
Отправить
galka

Спасибо! Ваша заявка принята

close
galka

Спасибо! Ваша заявка принята

close