Подсчет сортировки с изюминкой
Проблема: для несортированного массива чисел найдите максимальную разницу между последовательными элементами в его отсортированной форме. Числа могут быть отрицательными или десятичными.
Простой алгоритм
const maxGap = input => input .sort((a, b) => a — b) .reduce((acc, cur, idx, src) => Math.max(acc, idx > 0 ? cur — src[idx — 1] : 0), 0);
Эта функция сначала сортирует входные данные. Результатом является [9, 17, 21, 28, 41, 45]
для нашего примера. Затем он перебирает отсортированный массив и отслеживает максимальную разницу в переменной аккумулятора:
- макс (0, 0) = 0
- макс (0, 8) = 8
- макс (8, 4) = 8
- макс (8, 7) = 8
- макс (8, 13) = 13
- макс (13, 4) = 13
Сложность этого решения составляет O(n*log(n))
для сортировки и O(n)
для поиска максимальной разницы, что приводит к O(n*log(n))
. n
- количество элементов во входных данных. Любая сортировка сравнения имеет нижнюю границу O(n*log(n))
, поэтому мы не можем найти более быстрое решение с помощью сортировки сравнения - но есть решение этой проблемы с линейным временем. Давай найдем!
Решение с линейным временем
Сортировки сравнения, такие как mergesort, heapsort или quicksort, слишком медленны, если мы ищем решение с линейным временем. А счетная сортировка? Сортировка с подсчетом - это алгоритм целочисленной сортировки, который имеет сложность выполнения O(n+w)
и требует дополнительного пространства w
, где w
- максимальный элемент в несортированном массиве. Он хорошо работает, если целые числа маленькие. Сортировка с подсчетом использует второй массив длины w
, count или частотный массив.
Подсчет алгоритма сортировки
- Для каждого входа
i
увеличивайте значение индексаi
в массиве частот. - Перебрать частотный массив. Для каждого индекса, где значение больше 0 в массиве частот, поместите индекс в массив решений.
Заполнение частотного массива занимает O(n)
, итерация по частотному массиву и вставка элементов в отсортированный массив занимает O(w)
. Общее время выполнения составляет O(n+w)
.
К сожалению, обычная сортировка с подсчетом неприменима к нашей задаче, потому что
- числа могут быть отрицательными,
- числа могут быть числами с плавающей запятой и
- числа могут быть большими.
Но есть одно важное наблюдение, которое позволяет нам использовать модифицированную сортировку с подсчетом, которая выполняется в линейное время и требует линейного дополнительного пространства. Пусть max
и min
будут наибольшим и наименьшим числами ввода соответственно. Максимальная разница ограничена lowerBound = (max-min)/(n-1)
.
Используя это наблюдение, мы можем разделить диапазон чисел на (n-1)
сегментов длиной lowerBound
. Максимальный зазор не умещается в одном ведре.
Мы сопоставляем каждое число i
с его ведром. Сортировка по сегменту плохо работает, если числа сгруппированы, потому что числа в одном сегменте должны быть отсортированы. Мы обходим эту проблему, сохраняя только минимум и максимум в каждом сегменте. Мы можем опустить средние числа, потому что lowerBound
размером с ведро.
Мы находим максимальную разницу, перебирая массив сегментов длины (n-1)
, где каждый сегмент имеет не более двух записей.
Этот алгоритм работает в линейном времени, независимо от того, насколько далеко друг от друга находятся входные числа. Требуется линейное дополнительное пространство.
Представление
O(n)
быстрее, чем O(n*log(n))
для достаточно больших входов. Что это означает на практике для наших решений?
Для небольших входных данных с менее чем 10000
элементами простая функция, использующая array.prototype.sort()
, работает быстрее, чем линейный подход. Для больших входных данных линейный алгоритм работает быстрее. Например, для 10000000
элементов это занимает 4 секунды вместо 15 секунд.
Array with 1000 elements: n log(n) takes 0 seconds Linear takes 0.001 seconds Array with 10000 elements: n log(n) takes 0.012 seconds Linear takes 0.001 seconds Array with 5000000 elements: n log(n) takes 5.914 seconds Linear takes 1.793 seconds Array with 10000000 elements: n log(n) takes 15.611 seconds Linear takes 3.896 seconds
Заключение
Подсчетная сортировка - это алгоритм целочисленной сортировки, который выполняется в O(n)
. Все виды сравнения занимают не менее O(n*log(n))
.
Поскольку максимальная разница имеет нижнюю границу, мы можем использовать алгоритм линейного времени, разновидность сортировки с подсчетом и сортировки по сегменту.
Полный код находится на GitHub, а есть видео со мной на YouTube, где я кодирую решение в реальном времени.