Являются ли тесно связанные алгоритмы сортировки Radix Sort и Bucket Sort Adaptive?
Я знаю, что алгоритм сортировки называется адаптивным, если данные для сортировки предварительно отсортированы и алгоритм занимает минимальное время.
Однако я не могу сделать вывод, являются ли алгоритмы сортировки Radix и Bucket адаптивными или нет.
Алгоритм сортировки попадает в семейство адаптивной сортировки, если он использует существующий порядок ввода.
Например, сортировка вставками — это адаптивный алгоритм сортировки, если входные данные уже отсортированы, то временная сложность будет O (n).
В случае сортировки Bucket (или Bin sort) и сортировки Radix нет преимущества для порядка ввода. Временная сложность не зависит от порядка ввода. Вот почему они не являются адаптивным алгоритмом сортировки.
Примечание. Чтобы понять, относится ли алгоритм сортировки к семейству адаптивной сортировки, необходимо подумать о подходе к реализации, с помощью которого можно оптимизировать временную сложность на основе порядка ввода. Адаптивная сортировка обычно выполняется путем изменения существующих алгоритмов сортировки.
Надеюсь, поможет!
Ресурсы:
данные об адаптивной сортировке из Википедии
Адаптивный и неадаптивный алгоритм сортировки
