Как я уже упоминал в моих комментариях:
В вашем коде строки:
correct_index = min(len(item) - 1, col)
letter = ord(item[-(correct_index + 1)]) - min_base
Всегда использует первую букву слова один раз, col больше, чем длина слова. Это приводит к сортировке более коротких слов на основе их первой буквы, когда col больше длины слова. Например, ['aa', 'a'] остается неизменным, так как в течение слова col l oop мы сравниваем 'a' в обоих словах, что сохраняет результаты без изменений.
Исправление кода
Примечание. Попытка свести к минимуму изменения исходного кода
def count_sort_letters(array, size, col, base, max_len):
""" Helper routine for performing a count sort based upon column col """
output = [0] * size
count = [0] * (base + 1) # One addition cell to account for dummy letter
min_base = ord('a') - 1 # subtract one too allow for dummy character
for item in array: # generate Counts
# get column letter if within string, else use dummy position of 0
letter = ord(item[col]) - min_base if col < len(item) else 0
count[letter] += 1
for i in range(len(count)-1): # Accumulate counts
count[i + 1] += count[i]
for item in reversed(array):
# Get index of current letter of item at index col in count array
letter = ord(item[col]) - min_base if col < len(item) else 0
output[count[letter] - 1] = item
count[letter] -= 1
return output
def radix_sort_letters(array, max_col = None):
""" Main sorting routine """
if not max_col:
max_col = len(max(array, key = len)) # edit to max length
for col in range(max_col-1, -1, -1): # max_len-1, max_len-2, ...0
array = count_sort_letters(array, len(array), col, 26, max_col)
return array
lst = ['aa', 'a', 'ab', 'abs', 'asd', 'avc', 'axy', 'abid']
print(radix_sort_letters(lst))
Проверка
lst = ['aa', 'a', 'ab', 'abs', 'asd', 'avc', 'axy', 'abid']
print(radix_sort_letters(lst))
# Compare to Python sort
print(radix_sort_letters(lst)==sorted(lst))
Вывод
['a', 'aa', 'ab', 'abid', 'abs', 'asd', 'avc', 'axy']
True
Пояснение
Подсчет сортировки является стабильной сортировкой , что означает:
Давайте рассмотрим пример работы этой функции.
Давайте разберемся: ['a c', 'xb', 'ab']
Мы проходим каждый символ каждого список в обратном порядке.
Итерация 0:
Key is last character in list (i.e. index -1):
keys are ['c','b', 'b'] (last characters of 'ac', 'xb', and 'ab'
Peforming a counting sort on these keys we get ['b', 'b', 'c']
This causes the corresponding words for these keys to be placed in
the order: ['xb', 'ab', 'ac']
Entries 'xb' and 'ab' have equal keys (value 'b') so they maintain their
order of 'xb' followed by 'ab' of the original list
(since counting sort is a stable sort)
Итерация 1:
Key is next to last character (i.e. index -2):
Keys are ['x', 'a', 'a'] (corresponding to list ['xb', 'ab', 'ac'])
Counting Sort produces the order ['a', 'a', 'a']
which causes the corresponding words to be placed in the order
['ab', 'ac', 'xb'] and we are done.
Исходная ошибка программного обеспечения - ваш код изначально проходил слева направо через строки, а не справа налево. Нам нужно go справа налево, так как мы хотим отсортировать наш последний вид сортировки по первому символу, следующий за последним - по 2-му символу, et c.
Строки разной длины - в приведенном выше примере были строки одинаковой длины.
Предыдущий пример был упрощен при условии, что строки равной длины. Теперь давайте попробуем строки неравной длины, такие как:
['a c', 'a', 'ab']
Это сразу представляет проблему, так как слова не имеют равных длины, которые мы не можем выбрать букву каждый раз.
Мы можем исправить, заполнив каждое слово фиктивным символом, таким как '*', чтобы получить:
['a c', 'a *', 'ab']
Итерация 0: ключи - это последний символ в каждом слове, поэтому: ['c', '*', 'b']
The understanding is that the dummy character is less than all other
characters, so the sort order will be:
['*', 'b', 'c'] causing the related words to be sorted in the order
['a*', 'ab', 'ac']
Итерация 1: ключи располагаются рядом с последним символом в каждом слове, поэтому: ['a', 'a', 'a']
Since the keys are all equal counting sort won't change the order so we keep
['a*', 'ab', 'ac']
Removing the dummy character from each string (if any) we end up with:
['a', 'ab', 'ac']
Идея, лежащая в основе get_index должен имитировать c поведение строк заполнения без фактического заполнения (т.е. заполнение - это дополнительная работа). Таким образом, на основе индекса он оценивает, указывает ли индекс на дополненную или не дополненную часть строки и возвращает соответствующий индекс в массив для подсчета.