Что не так с моей сортировкой по основанию?

Примечание. Я использую Python 3.

Я пытаюсь отсортировать список слов в алфавитном порядке.

Это мой сорт:

def radix_sort(List, length):
    buckets = [[], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], []]
    for i in range (length-1, -1, -1):    #for every letter "column"
        for word in List:    #for every word 
            index = ord(word.azWord[i])-ord('a')   #get the index of the word
            buckets[index].append(word)     #add word object to correct bucket
    List[:] = []
    for containedList in buckets:
        List.extend(containedList)

Он используется в этом цикле:

for x in range(0,maxL):
    radix_sort(results[x], x)

maxL — это длина самых длинных слов, которые у меня есть, поэтому итерация от 0 до maxL проходит через весь список.

Мои результаты списка [] - это список списков. Каждый список в результатах содержит словесный объект, описанный следующим образом:

class word(object): #object class

    def __init__(self, originalWord=None, azWord=None, wLength=None):
        self.originalWord = originalWord
        self.azWord = azWord
        self.wLength = wLength

Например, results[3] должен содержать список всех слов с wLength равным 3.

Когда я подаю всю свою программу на следующий ввод:

hello
world
alphabetical
dog
cat
potato
stack

С помощью этого фрагмента кода:

for row in results:
    for item in row:
        print(item.originalWord)

Он печатает:

cat
cat
dog
dog
dog
cat
stack
stack
world
hello
hello
stack
hello
hello
world
hello
world
world
stack
stack
world
potato
potato
potato
potato
potato
potato
alphabetical

Я почти уверен, что правильно перебираю результаты [] при печати. Почему мой radix_sort не дает мне правильных результатов? Я пытался использовать отладчик, но не повезло.

РЕДАКТИРОВАТЬ: я изменил свой код следующим образом:

def radix_sort(List, length):
    for i in range (length-1, -1, -1): 
        for word in List:  
            buckets = [[], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], []]
            index = ord(word.azWord[i])-ord('a')  
            buckets[index].append(word)   
            List[:] = []   
    for containedList in buckets:  
        List.extend(containedList)
    return List #returns an alphabetized list

Теперь это дает мне ошибку здесь:

for containedList in buckets:

Он говорит: «UnboundLocalError: ссылка на локальную переменную« сегменты »перед назначением». Что это значит?


person Michi    schedule 03.04.2014    source источник
comment
buckets[index].append(word) вы добавляете каждое слово length раз в ведро.   -  person njzk2    schedule 03.04.2014
comment
О, Боже. Ты прав.   -  person Michi    schedule 03.04.2014
comment
в основном вам нужно переместить создание buckets внутри первого цикла, а также реконструкцию List.   -  person njzk2    schedule 03.04.2014
comment
Кажется, все работает нормально, если я просто вставлю List[:] = [] в цикл for word in List. Есть ли причина, по которой я должен переместить buckets, которого мне не хватает?   -  person Michi    schedule 03.04.2014
comment
если вы это сделаете, вы будете сортировать только по последней букве.   -  person njzk2    schedule 03.04.2014
comment
Теперь выдает ошибку. Смотрите правку в моем посте.   -  person Michi    schedule 03.04.2014
comment
Смотрите мой ответ. ваше объявление ведра теперь на один цикл слишком глубоко, и ваша реконструкция списка не переместилась.   -  person njzk2    schedule 03.04.2014


Ответы (3)


Следуя моим комментариям, это должно выглядеть так

def radix_sort(List, length):
    for i in range (length-1, -1, -1):    #for every letter "column"
        # Here buckets are created for each iteration
        buckets = [[], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], [], []]
        for word in List:    #for every word 
            index = ord(word.azWord[i])-ord('a')   #get the index of the word
            buckets[index].append(word)     #add word object to correct bucket
        # Here List is reconstructed for each iteration
        List[:] = []
        for containedList in buckets:
            List.extend(containedList)
person njzk2    schedule 03.04.2014
comment
Я понял. Теперь я вижу, где я ошибся. Большое спасибо. - person Michi; 03.04.2014

for i in range (length-1, -1, -1):    #for every letter "column"
    for word in List:    #for every word 
        index = ord(word.azWord[i])-ord('a')   #get the index of the word
        buckets[index].append(word)     #add word object to correct bucket

Давайте посмотрим на этот код. На первой итерации внешнего цикла вы помещаете все слова в ведра. На второй итерации вы помещаете все слова в ведра снова. Это происходит снова и снова на каждой последующей итерации; только когда вы все закончите, вы достаете слова из ведер и возвращаете их в исходный список.

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

person user2357112 supports Monica    schedule 03.04.2014
comment
Ага! Я пропустил отступ List[:] = [] немного дальше в цикле for word in List. Это решило проблему. Благодарю вас! - person Michi; 03.04.2014
comment
@Michi: Может показаться, что вы решили проблему, но, судя по вашему описанию, вы, похоже, изменили только то, как проявляется проблема. - person user2357112 supports Monica; 03.04.2014
comment
Я не понимаю, не могли бы вы объяснить, что вы имеете в виду? Кроме того, пожалуйста, смотрите мое редактирование выше. Похоже, проблема все еще существует. - person Michi; 03.04.2014
comment
@Michi: Вы переместили создание корзины и список опорожняющих частей слишком глубоко, и вы не изменили ту часть, в которой нуждались. Сегменты необходимо создавать заново, а список переупорядочивать на каждой итерации внешнего цикла. В настоящее время вы воссоздаете сегменты и очищаете список при каждой итерации внутреннего цикла, и вы возвращаете элементы в список только в самом конце, а не сразу после того, как вы очистите список. - person user2357112 supports Monica; 03.04.2014

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

buckets = [[] for i in range(26)]

Кроме того, есть еще один способ получить индекс корзины: вместо назначения переменной просто поместите эти вычисления в индекс.

buckets[((ord(letter)/10**i)%10) for letter in word]
person Pski17    schedule 11.04.2014