대기열을 사용하여 기수 정렬

Question

대기열을 사용하여 정렬을 수행하는 기수 정렬을 만들려고합니다. 내 큐 클래스에 사용하고 코드는 기본이지만, 작품 내 이해에

class Queue: 
    def __init__(self): 
     self.items = [] 

    def isEmpty(self): 
     return self.items == [] 

    def enqueue(self, items): 
     self.items.insert(0, items) #add item to the beginning 

    def dequeue(self): 
     return self.items.pop() # remove last item 

    def peek(self): 
     return self.items[len(self.items)-1] #First in line 

    def size(self): 
     return len(self.items) 

는 기수 정렬 (11 개) 총 쓰레기통을 사용합니다. 1 개의 저장소에는 모든 것이 들어 있습니다. 다른 10 개의 bin에는 0에서 9까지의 레이블이 지정됩니다. 첫 번째 정렬은 주 bin에서 1 개의 숫자를 제거하고 해당 숫자가 0 인 경우 1 자리의 숫자를보고 시작합니다. 0 인 경우 zero bin에 넣습니다. 1 우리는 하나의 빈에 넣는 등등. 메인 빈의 모든 숫자가 1의 자리 값으로 정렬 될 때까지 그렇게합니다. 그런 다음 0 빈에서 시작하여 해당 숫자를 꺼내 주 빈으로 다시 가져온 다음 10 자리에서 처리를 시작합니다. 수백 개 등등. Radix sort는 모든 데이터가 같은 길이 일 때만 작동합니다 (또는 말한 적이 있습니다.)

지금까지 Radix에 대해 이렇게했습니다. 나는 숫자 10 가능성이 6 자리의 값을 가지고 10 개 번호에 대해이 작업을 수행해야 할 것 깨달았 때문에

def radix(): 
    mainBin = Queue() 
    digList = [Queue()] * 10 #creates a list of 10 queues 

numberList = random.sample(range(100000,999999), 10) 
#This would normally be passed through, but this is easier for timing 
#the sort 

for num in numberList: 
    mainBin.enqueue(str(number)) 

while not mainBin.isEmpty(): 
    temporary = [] 
    number = mainBin.dequeue() 
    for digit in number: 
     temporary.append(digit) 
     if temporary[5] == '0': 
      digList[0].enqueue(temporary[5]) 

내가 첫 번째 if 문에서 멈췄다. 그 방법은 if-elif 체인의 길이에의 쓰기 (19 개 라인을 하나의 값으로 ...), 논리적으로 가장 먼저 떠오른 것이 었습니다. 누가 더 나은 해결책을 제시 할 수 있습니까?

Answer 1

대상 큐를 하드 코딩하는 대신 for 루프를 실행하고 인덱스를 사용할 수 있습니다. 아니 모든 자리 문자열이 동일한 길이이고

place = 6 # In this case you know it, but you could scan data to find it. 
while place >= 0: 
    while not mainBin.isEmpty(): 
     number = mainBin.dequeue() 
     digit = number[place] 
     digList[digit].enqueue(number) 

    place -= 1 


    # Reload mainBin logic goes here. 

케이스까지 연장하기 위해서는 적절한 제로와 패드 (당신이있는 소수점의 어느 쪽을 따라 다르다.) 수