Техника сортировки: пример радикальной сортировки

Question

Задача как это сделать?

Примените radix sort к следующему:

A = {cat,bat,cow,sit,may,why}

Answer 1

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

Когда вы начнете сортировку по основанию, ваши элементы будут назначены так:

{cat,bat,cow,sit,may,why}

В первой итерации мы будем идти сверху вниз и сортировать в алфавитном порядке по последней букве. Это приведет к:

{cat,bat,sit,cow,may,why}

В следующей итерации мы будем идти сверху вниз и сортировать в алфавитном порядке по второй или последней букве. Это приведет к:

{cat,bat,may,why,sit,cow}

Наконец, мы повторяем этот метод с первой буквы. Это приведет к вашим отсортированным словам:

{bat,cat,cow,may,sit,why}

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

Кроме того, время выполнения для этой сортировки по основанию будет O(L(n+k)), где L представляет длину ваших строк, а n представляет количество строк, которые вы должны отсортировать. K представляет диапазон значений, которые вы можете иметь. Если в ваших строках использовались только символы от "A" до "D", это было бы 4. Предполагая, что вы оцениваете весь алфавит, k будет представлено 26.

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