Эта статья является частью серии, посвященной алгоритмам сортировки в JavaScript. С остальной частью серии вы можете ознакомиться здесь. Если вы новичок в алгоритмах сортировки или алгоритмах в целом, сначала прочтите это, чтобы получить прочную основу для продвижения вперед. Сегодня я расскажу все, что вам нужно знать о сортировке по ведру.

Сортировка по корзине - это сортировка по распределению. Он работает, упорядочивая элементы по корзинам, которые затем сортируются с использованием другой сортировки. Обычно это использует сортировку вставкой, а затем объединяется в отсортированный список.

Сортировка по сегментам выполняется исключительно быстро, поскольку элементы стратегически назначаются сегментам. Обычно это достигается за счет использования массива, в котором индекс является значением. Это означает, что ради скорости требуется более высокая стоимость памяти.

Когда это быстро

Сортировка по ковшам лучше всего, когда она может равномерно распределять элементы по ковшам. Если значения распределяются редко, больший размер сегмента является более оптимальным, поскольку значения могут быть разделены более равномерно. Обратное также верно, когда плотно распределенный массив будет работать лучше с меньшим размером корзины.

Обычно вам следует использовать сортировку по корзинам только тогда, когда вы обычно знаете, что элементы будут равномерно распределены, и когда использование памяти не является проблемой.

Когда это медленно

Сортировка по сегментам работает в худшем случае, квадратично - O (n²), когда все элементы распределяются в одну корзину. В этом случае сортировка по корзине берет на себя сложность алгоритмов внутренней сортировки только в том случае, если необходимо отсортировать одну корзину.

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

Сложность

Временная сложность этого алгоритма в худшем случае квадратичная - O (n²). Средний случай, который, вероятно, имеет место, если вы имеете представление о размере и распределении входных данных, равен O (n + k).

Сложность пространства вспомогательная - O (n + k).

Упрощенный псевдокод

Import some type of insertion sort to use in bucket sort function
Create bucketSort function (array, bucket size)
  Create vars for i, min, max, and bucket size
  Find min and max value
  Create amount of buckets
  Push values to correct buckets 
  Sort buckets

Код

Обычная реализация сортировки по сегментам работает путем разделения массива размером n на k сегментов, которые содержат определенный диапазон значений элементов. Эти сегменты затем сортируются с использованием алгоритма сортировки, который может быть выбран на основе ожидаемого размера входных данных.

Этот пост написал один из инструкторов Banyan Codecamp, нового учебного курса по программированию, разработанного с единственной целью: превратить начинающих программистов в способных инженеров под руководством старших инженеров. Получи высшее образование, сделай шестизначное число и учись на прекрасном острове Бали. Чтобы узнать больше, посетите www.codeinbali.com.