DjangoBB LoFi version

Полная версия: Сортировка списка с помощью radixsort

Начало » Центр помощи » Сортировка списка с помощью radixsort

jheniae

Май 25, 2015 16:58:54

Здравствуйте. Помогите пожалуйста с задачей, условие следующее:
на вход дан массив длиной 1000 элементов, каждый элемент состоит из трех символов латиницы, в произвольном порядке. Задача отсортировать массив в алфавитном порядке с помощью алгоритма поразрядной сортировки в качестве внутреннего алгоритма следует использовать алгоритм сортировки подсчетом.

def CountingSort(A,k,d):
    B=[0]*len(A)
    C=[0]*(k)
    for j in range(0,len(A)):
        C[ord(A[j][d])-97]+=1
    for h in range(1,k):
        C[h]+=C[h-1]
    for i in range((len(A)-1),-1,-1):
        B[C[ord(A[i][d])-97]]=A[i]
        C[ord(A[i][d])-97]-=1
    return B
def RadixSort(A,d):
    arr=A
    for i in range(d-1,-1,-1):
        arr=CountingSort(arr,26,i)
    return arr

Мой код выдает ошибку " B[C[ord(A)-97]]=A
IndexError: list assignment index out of range" , уже бьюсь довольно много и не могу понять где происходит ошибка. Буде благодарен хоть за какой то намек. Спасибо.

FishHook

Май 25, 2015 17:16:46

for j in range(0,len(A)-1):

terabayt

Май 25, 2015 17:35:36

B[C[ord(i[d])-97]-1]=i

вот подумайте и все станет ясно почему нужно добавить -1

def CountingSort(A, k,  d):
    B = [0]*len(A)
    C = [0]*(k)
    for j in A:
        C[ord(j[d])-97] += 1
    for h in range(1, k):
        C[h] += C[h-1]
    for i in reversed(A):
        B[C[ord(i[d])-97]-1] = i
        C[ord(i[d])-97] -= 1
    return B
def RadixSort(A, d):
    arr = A
    for i in range(d-1, -1, -1):
        arr = CountingSort(arr, 26, i)
    return arr

немного ностальгии по reduce

def RadixSort(A, d):
    return reduce(lambda a, i: CountingSort(a, 26, i), range(d-1, -1, -1), A)

jheniae

Май 25, 2015 19:00:30

FishHook
for j in range(0,len(A)-1):

Но ведь тогда, элемент с индексом 999 не будет обрабатываться циклом.

jheniae

Май 25, 2015 19:26:31

terabayt

terabayt
вот подумайте и все станет ясно почему нужно добавить -1

Потому что список B имеет 1000 элементов а индексации начинается с нуля, правильно?

terabayt

Май 25, 2015 19:41:18

jheniae
Потому что список B имеет 1000 элементов а индексации начинается с нуля, правильно?

потому что в В вы хотите хранить список с len(A) элементов но при этом не учитываете что C[ord(i)-97] никогда не будет равен 0
значит вы никогда не будете обращаться к нулевому элементу
нужно или создавать

B = len(A) + 1

и при этом откидывать первый элемент или делать как я сделал

работает мой вариант?
у меня работает

>>> def CountingSort(A, k, d):
...     B = [0]*len(A)
...     C = [0]*(k)
...     for j in A:
...         C[ord(j[d])-97] += 1
...     for h in range(1, k):
...         C[h] += C[h-1]
...     for i in reversed(A):
...         B[C[ord(i[d])-97]-1] = i
...         C[ord(i[d])-97] -= 1
...     return B
... 
>>> def RadixSort(A, d):
...     return reduce(lambda a, i: CountingSort(a, 26, i), range(d-1, -1, -1), A)
... 
>>> print RadixSort(['zbc', 'aol', 'acb'], 3)
['acb', 'aol', 'zbc']

FishHook

Май 25, 2015 19:43:38

jheniae
Потому что список B имеет 1000 элементов а индексации начинается с нуля, правильно?

Бинго!

jheniae

Май 26, 2015 12:35:27

Спасибо огромное всем за помощь.
terabayt
Да действительно, я не учел, что цикл не присвоит значение с нулевым индексом. Спасибо за подсказку, теперь я понял, и все работает.