Быстрая сортировка массива в JS
Из этого урока вы узнаете об одном из самых популярных алгоритмов сортировки массивов – Быстрая сортировка (Quick sort).Как работает алгоритм быстрой сортировки и в чем основная его идея?
Из массива случайным или неслучайным образом выбирается опорный элемент (чаще всего из середины массива), с которым сравниваются все остальные элементы. Все элементы, которые меньше опорного, передвигаются влево. А те элементы, которые больше опорного или равные, передвигаются вправо. Фактически создаются два новых массива с меньшими и большими значениями относительно опорной точки. Затем мы рекурсивно выполняем ту же последовательность операций для новых массивов. В результате будут возвращены оба новых подмассива плюс опорная точка в уже отсортированном виде.
Пример быстрой сортировки
Создадим массив, состоящий из чисел и присвоим его переменной arr.
const arr = [1, 200, 4, 6, 2, 8, 7];
Убедимся, что в массиве находится больше чем один элемент. Для этого создадим условие: если длина массива меньше чем 2, то вернется сам массив. Сортировка не сработает если в массив пустой или с одним элементом.
const qsort = (arr) => {
if (arr.length < 2) {
return arr;
}
В нашем массиве больше чем один элемент, значит двигаемся дальше. Случайным образом вычислим опорную точку, относительно которой будет делиться массив на две части. В переменную pivotPosition отправится результат вычислений следующей формулы: случайное значение, умноженное на длину массива. Так мы получим в качестве опорной точки, примерно средний элемент на всей длине массива.
else {
// Опорная точка для деления массива, выбирается случайно
const pivotPosition = Math.floor(Math.random() * arr.length);
const pivot = arr[pivotPosition];
Собираем новый массив из значений, которые меньше и равные поворотной точки. Пропускаем текущий массив через фильтр.
// Значения меньшие, либо равные опорному
// попадают в новый массив less
const less = arr.filter((value, index) => {
const isPivot = index === pivotPosition;
return !isPivot && (value <= pivot);
});
Делаем тоже самое для значений, которые больше чем поворотная точка.
// Значения, которые больше опорного
// попадают в новый массив less
const more = arr.filter(value => value > pivot);
Собираем массив заново - пропускаем меньший и больший массив через qsort, между ними прописываем поворотную точку. Нам вернется новый массив, состоящий из отсортированных массивов less, more и поворотной точки.
return [...qsort(less), pivot, ...qsort(more)];
}};
Наш массив отсортирован по возрастанию с помощью алгоритма быстрой сортировки.
console.log(qsort(arr));
Это и есть алгоритм быстрой сортировки. Мы берем какой-то элемент массива (контрольный), разбиваем все оставшиеся элементы массива на те, которые больше и на те, которые меньше контрольного элемента. Затем проводим ту же самую быструю сортировку над всеми элементами из большего и меньшего массива. С помощью алгоритма быстрой сортировки, можно быстрее отсортировать массив, чем обычным методом sort.
Метод sort
Когда вам не нужна быстрая сортировка, то можно воспользоваться более простым способом сортировки - методом sort. С помощью метода sort, для сортировки массива по возрастанию потребовалось всего три строчки кода.
const array = [1, 200, 4, 6, 2, 8, 7];
const newArray = array.sort((a, b) => a-b);
console.log(newArray); // [1, 2, 4, 6, 7, 8, 200]
-
Создано 22.07.2020 10:23:47
-
Михаил Русаков
Комментарии (0):
Для добавления комментариев надо войти в систему.
Если Вы ещё не зарегистрированы на сайте, то сначала зарегистрируйтесь.