0

キューを使用してリストを適切に基数ソートするにはどうすればよいですか？

私はPython3xを使用しています。

キューは先入れ先出しのデータ構造であるため、これはキューをビンとして使用する私の試みです。

from my_queue import Queue
def rsort(n):
    '''(list of int) -> list of int
    '''
    list_length = len(n)
    val = 0
    mod = 10
    k = 1
    bin_list = []
    alist = n
    for bins in range(0,10):
        bin_list.append(Queue())

    while val == 0:
        for num in alist:
            sig_dig = num % mod
            sig_dig = int(sig_dig / k)
            bin_list[sig_dig].enqueue(num)

        if bin_list[0].size() == list_length:
            alist.append(bin_list[0].dequeue())

        else:
            mod = mod * 10
            k = k * 10            

        new_list = []
        for bins in bin_list:
            if not bins.is_empty():
                new_list.append(bins.dequeue())
            alist = new_list

        return alist

私のコードは、次のような小さな数値でも完全に機能します。[3,2,6,5,8,7]

ただし、リスト内の値が次のように大きくなる場合：[240, 28, 5, 18, 140, 2]

私のプログラムはリストをソートしなくなり、番号が欠落して順序付けされなくなります。

私は自分のプログラムでたくさん遊んでいますが、それを修正することはできません:(

4

1 に答える 1

1

コードに間違っていると思われることがいくつかあります。これらのどれがあなたが見ている問題を引き起こしているのか正確にはわかりませんが、正しい結果を得るにはおそらくすべてを修正する必要があります。

まず、簡単なメモ：1つの整数を使用して各数値の正しい桁を見つけるだけで、ロジックを少し単純化できます。ゼロから始まり、ある値（ソートする桁数）まで上がる値をお勧めします。特定のリストアイテムのその桁の値は、で見つけることができますsig_dig = num // 10**k % 10。演算子は、//Pythonに「床除算」を使用させ、通常の除算の非整数部分を切り捨てます。

とにかく、最初の問題は、ループしていることですがval == 0、を変更することはなくval、ループが終了する前に値を返します（したがって、とにかく2回以上行うことはありません）。これを修正するには、リストの最長値の桁数を。のように計算しますmax_digits = int(math.ceil(math.log(max(lst), 10)))。次に、ループをはるかに簡単にすることができます。for k in range(max_digits):

私が見る次の問題は、おそらくビンから値をリストに正しく戻していないということです。呼び出しているdequeueのは1回だけですが、キューが空になるまで繰り返し呼び出す必要があります。Queueまたは、使用しているAPIを誤解して、dequeueすべてのキューの値を返す場合は、を使用extendしてそれらすべてを一度にリストに追加する必要があります。

最後に、あなたが欲しいと思うものは次のとおりです。

import math

from my_queue import Queue

def rsort(n):
    '''(list of int) -> list of int
    '''
    bin_list = [Queue for _ in range(10)]
    max_digits = int(math.ceil(math.log(max(lst), 10))) # calculate # of digits

    for k in range(max_digits):
        for num in alist:
            sig_dig = num / 10**k % 10 # find digit's value
            bin_list[sig_dig].enqueue(num)

        n = [] # we can reuse the name `n`, rather than using a different name
        for bins in bin_list:
            while not bins.is_empty(): # loop to dequeue all values
                n.append(bins.dequeue())

    return n # the return statement is outside the loop!
于 2013-03-21T13:04:20.757 に答える