Основные возможности платформы Hexlet не доступны в вашем браузере.
Пожалуйста, обновитесь. Выбрать браузер.

Испытания

↳ Быстрая сортировка

JS: Последовательности

sort.js

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

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

Алгоритм

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

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

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

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

Начать Успешных завершений: 74%

Последние код-ревью

Автор Дата обновления Версий
user-124d23806439559b 17 февр., 14:52 1
dmhlupin 12 февр., 13:28 1
jazz 08 февр., 12:17 2
li0n0k 07 февр., 07:50 1
user-2685728d555627d4 06 февр., 20:42 1