Подсчет сортировки с изюминкой

Проблема: для несортированного массива чисел найдите максимальную разницу между последовательными элементами в его отсортированной форме. Числа могут быть отрицательными или десятичными.

Простой алгоритм

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).

К сожалению, обычная сортировка с подсчетом неприменима к нашей задаче, потому что

  1. числа могут быть отрицательными,
  2. числа могут быть числами с плавающей запятой и
  3. числа могут быть большими.

Но есть одно важное наблюдение, которое позволяет нам использовать модифицированную сортировку с подсчетом, которая выполняется в линейное время и требует линейного дополнительного пространства. Пусть 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, где я кодирую решение в реальном времени.