대기열을 사용하여 기수 정렬 방법?

Question

대기열을 사용하여 목록을 올바르게 기수 정렬하려면 어떻게합니까?

저는 파이썬 3x를 사용하고 있습니다.

대기열은 선입 선출 데이터 구조이기 때문에 대기열로 쓰는 것은 저의 시도입니다. 목록에서 값이 같은 큰 될 때 [3,2,6,5,8,7]

:하지만

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 

내 코드는 작은 숫자와 완벽하게 잘 작동 [240, 28, 5, 18, 140, 2]

내 프로그램이 더 이상 목록을 정렬

, 숫자가 누락 끝 없다 정렬되지 않은.

내 프로그램을 많이 사용 해본하지만 난 그냥 :(해결할 수없는

코드에서 잘못된 것 몇 가지가 있습니다

Answer 1

. 나는 정확히 모르겠어요 어떤의 이것들은 현재보고있는 문제를 일으키는 것이지만 올바른 결과를 얻으려면 모든 문제를 해결해야 할 것입니다.

먼저, 간단한 참고 사항 : 단일 정수만 사용하여 논리를 단순화 할 수 있습니다 각 숫자에서 올바른 숫자를 찾으려면 0에서 시작하여 정렬하려는 숫자의 숫자까지 올라가는 값을 제안하십시오. 주어진 목록 항목의 숫자 값은 sig_dig = num // 10**k % 10입니다 . // 연산자는 파이썬이 "floor division"을 사용하도록 강제하며, 정상적인 나눗셈의 비 - 정수 부분을 잘라냅니다.

어쨌든, 첫 번째 문제는 을 반복하고 있지만 절대로 val을 수정하지 않고 루프가 끝나기 전에 값을 반환합니다 (어쨌든 한 번 이상 반복하지 않으므로). max_digits = int(math.ceil(math.log(max(lst), 10)))과 같이 목록의 가장 긴 값의 자릿수를 계산하여 문제를 해결할 수 있습니다. 그렇다면 루프를 훨씬 간단하게 만들 수 있습니다. for k in range(max_digits):

다음 호의 내용은 빈 목록의 값을 목록으로 올바르게 가져 오지 못했기 때문입니다. dequeue 한 번만 호출하지만 대기열이 비어있을 때까지 반복해서 호출해야합니다. 또는 사용중인 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!