Количество «сегментов» в сортировке сегментов соответствует и зависит от диапазона возможных значений, которые должны быть отсортированы .Например, если я рассматриваю следующие значения:
1, 4, 10000, 5, 12
Диапазон значений, которые я сортирую, равен 9999.
range = (highest value) - (lowest value) = 10000 - 1 = 9999 buckets
Это означает, что мне потребуется 9999 корзин для сортировкиэти значения максимально эффективно.Это связано с тем, что Bucket Sort НЕ является сравнением.Это означает, что значения не сравниваются друг с другом, чтобы определить их порядок.Они просто помещаются в ведра, которые представляют их значения.Из-за этого сортировка ведра считается равной O (n) , но на самом деле она имеет тенденцию быть гораздо менее эффективной из-за количества блоков, которые необходимо создать.
В предыдущем примере мы сортировали только 5 значений, но нам нужно было создать более 10000 сегментов.Это крайне неэффективно, когда объемы сегментов находятся во временных сложностях O (N ^ 2) , что делает сортировку сегментов такой же дорогостоящей по времени (если не хуже), чем традиционные алгоритмы сортировки сравнения.Однако, если условия являются правильными, то сортировка по ковшам может быть хорошим выбором.