BLACK FRIDAY

осталось 4 дня

Скидка 10% и подарок на выбор — при покупке одной программы
При покупке двух программ  — вторая со скидкой 50%

Javascript: Быстрая сортировка

JS: Последовательности 62 сообщения
Обновлено: 14 сент., 06:24
1253
Студента
78%
Завершения

sort.js

Реализуйте и экспортируйте по умолчанию функцию, которая принимает на вход список и сортирует его по возрастанию.

Примеры:

sort(l(3, 3, 0, -1, 0, 4, -5));
// (-5, -1, 0, 0, 3, 3, 4)

sort(l(5, -3, 2, 10, 4, 4, 5));
// (-3, 2, 4, 4, 5, 5, 10)

Алгоритм

Быстрая сортировка, сортировка Хоара (англ. quicksort), часто называемая qsort (по имени в стандартной библиотеке языка Си) — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром во время его работы в МГУ в 1960 году.

Общая идея алгоритма состоит в следующем:

  1. Выбрать из списка элемент, называемый опорным. Это может быть любой из элементов списка или же число, вычисленное на основе значений элементов.
  2. Сравнить все остальные элементы с опорным и переставить их в списке так, чтобы разбить список на три непрерывных отрезка, следующих друг за другом: «меньшие опорного», «равные» и «большие».
  3. Для отрезков «меньших» и «больших» значений выполнить рекурсивно ту же последовательность операций, если длина отрезка больше единицы.

На практике список обычно делят не на три, а на две части: например, «меньшие опорного» и «равные и большие»; такой подход в общем случае эффективнее, так как упрощает алгоритм разделения.

Для полного доступа к испытанию нужен базовый план

Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.

Получить доступ
1000
упражнений
2000+
часов теории
3200
тестов

Отзывы

Аватар пользователя Андрей Никитин
Андрей Никитин 19 ноября 2017

Хороша задача... Решил ее без head и tail. Хотя мысли были их применить, не захотел. Пошел по пути среднего значения всего списка. Кроме расчета среднего на каждом шаге, пришлось еще и проверку на одинаковые значения придумывать, т.к. рекурсия улетает в infinity)) Хоть код и рабочий, но бестолковый) Мы не ищем легких путей ))