Сортировка по основанию Python

Я пытаюсь реализовать сортировку Radix в python.

Моя текущая программа работает неправильно в том смысле, что список типа [41,51,2,3,123] будет правильно отсортирован до [2,3,41,51,123], но что-то вроде [52,41,51,42,23] станет [23,41,42,52,51] (52 и 51 не на месте).

Я думаю, что знаю, почему это происходит, потому что, когда я сравниваю цифры десятков, я также не сравниваю единицы (то же самое для более высоких степеней 10).

Как исправить эту проблему, чтобы моя программа работала максимально быстро? Спасибо!

def radixsort(aList):
    BASEMOD = 10
    terminateLoop = False
    temp = 0
    power = 0
    newList = []
    while not terminateLoop:
        terminateLoop = True
        tempnums = [[] for x in range(BASEMOD)]

        for x in aList:
            temp = int(x / (BASEMOD ** power))
            tempnums[temp % BASEMOD].append(x)
            if terminateLoop:
                terminateLoop = False


        for y in tempnums:
            for x in range(len(y)):
                if int(y[x] / (BASEMOD ** (power+1))) == 0:
                     newList.append(y[x])
                     aList.remove(y[x])



        power += 1

    return newList

print(radixsort([1,4,1,5,5,6,12,52,1,5,51,2,21,415,12,51,2,51,2]))

python radix-sort
person ytpillai    schedule 15.02.2016    source источник
comment
Если бы вас заботила скорость, вы бы не создавали свой собственный вид.   -  person Steven Rumbalski    schedule 16.02.2016
comment
Я пытаюсь сделать самую быструю сортировку, которую я могу   -  person ytpillai    schedule 16.02.2016
comment
По сути, я не хочу, чтобы это было O (n ^ 2) или что-то в этом роде.   -  person ytpillai    schedule 16.02.2016
comment
Просто чтобы уточнить, вы понимаете, что вы не получите сортировку быстрее, чем встроенная, верно?   -  person Steven Rumbalski    schedule 16.02.2016
comment
Да, я не сторонник скорости, но я хочу, чтобы это было примерно нормальное время для программы счисления.   -  person ytpillai    schedule 16.02.2016
comment
Время на самом деле не имеет значения, я больше ищу эффективный алгоритм   -  person ytpillai    schedule 16.02.2016
comment
Недавно другой вопрос касался самых быстрых алгоритмов сортировки (но на основе np.ndarray). Может быть, это поможет.   -  person MSeifert    schedule 16.02.2016
comment
Моя цель - научиться и понять, как написать хорошую систему счисления, а не использовать ее для других целей.   -  person ytpillai    schedule 16.02.2016

Ответы (2)


arrow_upward
2
arrow_downward

В настоящее время ваша сортировка ничего не делает для переупорядочения значений на основе чего-либо, кроме их старшей цифры. Вы получаете правильные 41 и 42 только случайно (поскольку они находятся в правильном относительном порядке в исходном списке).

Вы всегда должны создавать новый список на основе каждого цикла сортировки.

def radix_sort(nums, base=10):
    result_list = []
    power = 0
    while nums:
        bins = [[] for _ in range(base)]
        for x in nums:
            bins[x // base**power % base].append(x)
        nums = []
        for bin in bins:
            for x in bin:
                if x < base**(power+1):
                    result_list.append(x)
                else:
                    nums.append(x)
         power += 1
     return result_list

Обратите внимание, что сортировка по основанию не обязательно быстрее, чем сортировка на основе сравнения. Он имеет меньшую сложность только в том случае, если количество сортируемых элементов превышает диапазон значений элемента. Его сложность O(len(nums) * log(max(nums))), а не O(len(nums) * log(len(nums))).

person Blckknght    schedule 16.02.2016

arrow_upward
1
arrow_downward

Поразрядная сортировка сортирует элементы, сначала группируя отдельные цифры одного и того же разряда. [2,3,41,51,123] сначала мы группируем их по первым цифрам.

[[],[41,51],[2],[3,123],[],[],[],[],[],[]]

Затем отсортируйте элементы в порядке возрастания/убывания. новый массив будет

[41,51,2,3,123]

то мы будем сортировать по десятой цифре. в этом случае [2,3]=[02,03]

[[2,3],[],[123],[],[41],[51],[],[],[],[]]

теперь новый массив будет

    [2,3,123,41,51]

наконец, на основе 100-х цифр. на этот раз [2,3,41,51]=[002,003,041,051]

  [[2,3,41,51],[123],[],[],[],[],[],[],[],[]]

наконец, мы получаем [2,3,41,51,123]

def radixsort(A):
    if not isinstance(A,list):
        raise TypeError('')
    n=len(A)
    maxelement=max(A)
    digits=len(str(maxelement)) # how many digits in the maxelement
    l=[]
    bins=[l]*10 # [[],[],.........[]] 10 bins
    for i in range(digits):
        for j in range(n): #withing this we traverse unsorted array
            e=int((A[j]/pow(10,i))%10)
            if len(bins[e])>0:
                bins[e].append(A[j]) #adds item to the end
            else:
                bins[e]=[A[j]]
        k=0 # used for the index of resorted arrayA
        for x in range(10):#we traverse the bins and sort the array 
            if len(bins[x])>0:
                for y in range(len(bins[x])):
                    A[k]=bins[x].pop(0) #remove element from the beginning
                    k=k+1
person Yilmaz    schedule 18.12.2020