Является ли radix sort единственным алгоритмом сортировки без сравнения?

Как видно из заголовка, является ли radix sort единственным алгоритмом сортировки без сравнения? Я думаю, да.

Источник

2 ответа

Решение

Нет, среди прочего есть и сортировка ведра. Проверьте статью в Википедии для получения дополнительной информации.

Источник

Любой набор можно отсортировать, не используя сравнения.

Процесс

  • выберите управляемый размер входного домена M, который вы можете обработать для записи в управляемый массив. Для символов (8 бит) домен будет 0-255.
  • разбить входные данные в некотором порядке в массив.
  • повторить и промыть, если вход еще не учтен полностью, т.е. все биты в M не были учтены.

Например, 32-разрядная целочисленная сортировка M может быть выполнена как:

  • посмотрите на первые 8 бит, поместите (ссылки, указатели или то, что доступно вашему языку) в 8-битный диапазон. поместите их в массив [0-255], теперь у вас есть грубый (приблизительный) порядок ваших значений.
  • посмотрите на следующие 8 битов, поместите их в похожий массив, сохраните ссылку на первый порядок. Следующие 8x2 бит обрабатываются аналогичным образом. Для извлечения вы переходите по ссылкам из первого набора.

Radix sort использует цифры и имеет 2 варианта (от MSB до LSB) и (от LSB до MSB).

Подсчет сортировки использует только первый шаг

Сортировка ведра обычно упоминается, когда речь идет о смешанных видах подсчета и сравнения.

Интересно, что для довольно многих случаев использования сортировки сравнений не хватает.

Источник
Другие вопросы по тегам