☕ Объясняем алгоритм быстрой сортировки с помощью JavaScript
Работаю в ИТ 6+ лет в сфере разработки ПО для мобильных устройств. Преимущественно работаю с экосистемой Apple. Разрабатываю для iPhone, iPad, iWatch. Раскладываем по полочкам, как работает алгоритм быстрой сортировки с помощью JavaScript с пошаговой иллюстрацией каждого шага. Быстрая сортировка (англ. quicksort) – это метод сортировки значений в списке в последовательные списки с помощью повторяющейся процедуры. В методе быстрой сортировки выбирается значение из основного списка, которое называется опорным значением. Остальные значения разделяются на два списка: Метод быстрой сортировки повторяется для всех результирующих списков, пока не останется только одно значение или пустой список значений. После этого вы выбираете последнее одиночное значение, и если значение располагается слева от опорного значения, оно остается таким, пока вы не дойдете до первого опорного значения вверху. У вас есть список значений, как показано ниже: Что вы хотите сделать, так это упорядочить значения от наименьшего к наибольшему. Как это сделать? Первое что нужно сделать – это выбрать одно значение и сделать его опорным значением. Выберем число 47. Следующее, что вы должны сделать – поместить значения, которые меньше или равны 47 с левой стороны. Значения больше 47 будут располагаться справа: Теперь вы будете повторять тот же процесс, пока не останется только одно значение или пустой список значений. Следующий шаг – начать со списков отдельных значений. Затем поместить значение слева от опорного значения, если оно уже находится слева, или поместите его справа, если оно уже находится справа. Вот как будут выглядеть окончательные результаты: Как видно из результатов, значения были расположены от наименьшего к наибольшему. Метод быстрой сортировки с помощью Javascript Первое что вы сделаете – это определите переменную для значений, используя assignment.js Затем вы создадите функцию, которая будет сортировать значения списка при ее вызове. Для этого сначала нужно объявить функцию: assignment.js Функция Следующее, что вы сделаете – это проверите длину списка. Если длина равна assignment.js Давайте теперь выберем опорное значение и создадим два пустых списка. Назовем один список assignment.js Как видно из приведенного выше блока кода, опорное значение будет последним значением из нашего списка значений, которые вы определили на первом шаге. Два пустых списка будут использованы для хранения значений, которые вы сравниваете с опорным значением. Если значение меньше или равно опорному значению, то оно будет храниться в Чтобы реализовать это, воспользуемся циклом assignment.js Теперь вызовем Оператор расширения (англ. spread operator) позволит нам быстро скопировать все или часть существующего списка в другой список. assignment.js Чтобы проверить, работает код или нет, вызовем функцию assignment.js Чтобы увидеть результат, нужно создать HTML-файл и подключить к нему JavaScript-файл, который вы написали выше. index.html После этого откройте HTML-файл в браузере. Затем кликните правой кнопкой мыши на странице и выберите Затем перейдите в консоль и вы увидите, что наши значения отсортированы от наименьшего к большему. *** Метод быстрой сортировки очень эффективный метод, который обеспечивает Пример доступен на Github! *** Больше полезных материалов вы найдете на нашем телеграм-канале «Библиотека фронтендера» Интересно, перейти к каналу itelenkov
const
.
const values = [2, 27, 14, 52, 31, 96, 73, 47, 22, 6];
function QuickSort(List) { }
QuickSort
принимает один параметр, называемый List
. 1
, тогда вы возвращаете список как есть:
function QuickSort(List) { if(List.length <= 1) { return List; } }
leftList
, а другой список – rightList
.
function QuickSort(List) { if (List.length <= 1) { return List; } const pivot = List[List.length - 1]; const leftList = []; const rightList = []; }
leftList
. Если значение больше, чем опорное значение, то оно будет храниться в rightList
. for
, как показано ниже.
function QuickSort(List) { if (List.length <= 1) { return List; } const pivot = List[List.length - 1]; const leftList = []; const rightList = []; for (let i = 0; i < List.length - 1; i++) { if (List[i] < pivot) { leftList.push(List[i]); } else { rightList.push(List[i]) } } }
QuickSort
в списке leftList
и rightList
, чтобы разделить их и полностью отсортировать. Чтобы сделать это, используйте оператор расширения из Javascript.
function QuickSort(List) { if (List.length <= 1) { return List; } const pivot = List[List.length - 1]; const leftList = []; const rightList = []; for (let i = 0; i <= List.length - 1; i++) { if (List[i] < pivot) { leftList.push(List[i]); } else { rightList.push(List[i]) } } return [...QuickSort(leftList), pivot, ...QuickSort(rightList)]; }
QuickSort
на нашем списке значений и посмотрим, будут ли они упорядочены от наименьшего к большему.
const values = [2, 27, 14, 52, 31, 96, 73, 47, 22, 6]; function QuickSort(List) { if (List.length <= 1) { return List; } const pivot = List[List.length - 1]; const leftList = []; const rightList = []; for (let i = 0; i < List.length - 1; i++) { if (List[i] < pivot) { leftList.push(List[i]); } else { rightList.push(List[i]) } } return [...QuickSort(leftList), pivot, ...QuickSort(rightList)]; } console.log(QuickSort(values));
<!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <meta http-equiv="X-UA-Compatible" content="IE=edge"> <meta name="viewport" content="width=device-width, initial-scale=1.0"> <title>Document</title> </head> <body> <script src="./assignment.js"></script> </body> </html>
Inspect
из списка опций.O(nlog(n))
производительность в среднем и его относительно легко реализовать.Материалы по теме
- 0 views
- 0 Comment
Свежие комментарии