14. 큐로 데이터 정렬하기 (기수 정렬) 파이썬

큐(queue)로 기수 정렬(radix sort) 하기

 

데이터를 정렬할 때도 큐를 이용할 수 있습니다.

 

아주 예전 컴퓨터에 프로그램을 입력할 때 천공(펀치) 카드를 사용했죠.

(디스켓 세대인 저도 이건 교과서에서나 볼 수 있었습니다.)

 

펀치 카드 정렬할 때
카드를 보관하는 통을 이용했다고 합니다. 

 

An IBM card sorter performing a radix sort on a large set of  punched cards . https://en.wikipedia.org/wiki/Radix_sort

 

예를 들어서 설명하겠습니다. 

다음 번호가 찍혀 있는 천공 카드가 있다고 가정하겠습니다. 

34, 56, 86, 46, 13, 51, 38, 54

 

1. 첫 번째 (1의) 자리부터 분류합니다.

 

첫 번째 자리의 숫자와 같은 번호가 붙어 있는 바구니에 담으면 됩니다. 
10진수니까 10개의 바구니가 필요합니다. 

0번 바구니: 
1번 바구니: 51
2번 바구니:
3번 바구니: 13 
4번 바구니: 34, 54
5번 바구니: 
6번 바구니: 56, 86, 46
7번 바구니: 
8번 바구니: 38
9번 바구니: 

다 담고 나서는 제대로 분류가 되었는지 첫 번째 자리의 구멍을 빛이나 꼬챙이로 확인했겠죠. (아님 말고..)

분류된 카드를 '0번 바구니부터 순서대로 모아서' 한 바구니에 담습니다. 

 

2. 2번째 (10의) 자리 분류

 

같은 요령으로 즉 두 번째 자리의 숫자와 같은 번호가 붙어있는 바구니에 담으면 됩니다. 

0번 바구니: 
1번 바구니: 13
2번 바구니:
3번 바구니: 34, 38
4번 바구니: 46
5번 바구니: 51, 54, 56
6번 바구니: 
7번 바구니: 
8번 바구니: 86
9번 바구니: 

0번 바구니부터 확인하면 숫자가 정렬된 것을 볼 수 있죠?
이제 카드를 0번 바구니부터 차례대로 한 바구니에 모으면 끝입니다. 

 

이제 큐를 이용해 코딩해 봅시다. 
하나의 바구니를 하나의 큐로 코딩하면 됩니다. 

 

코딩의 편의를 위해 조건을 설정합시다. (감만 잡고 넘어가죠 ㅎㅎㅎ)

2자리의 양의 정수를 기수 정렬하시오. 
34, 56, 86, 46, 13, 51, 38, 54

 

1. 이번에는 colcollections. deque를 사용했습니다. 

 

2. 분류(distribute)해주는 함수와 모으는(collect) 함수를 분리했습니다. 

 

3. 리스트에 deque()를 append 할 수 있습니다.

deque()를 baskets리스트에 append 하면 deque 클래스에서 정의된 메서드들을 baskets[0].popleft() 형식으로 사용할 수 있게 됩니다. 

혹시 파이참을 쓰신다면 deque에 커서를 두고 ctrl + b를 누르면 클래스의 선언부(declaration)를 바로 볼 수 있습니다. 

from collections import deque


def radix_sort(nums):
    
    baskets = []
    for _ in range(10):
        baskets.append(deque())

    distribute(nums, baskets, 0)
    collect(nums, baskets)
    print(nums)
    distribute(nums, baskets, 1)
    collect(nums, baskets)
    print(nums)


def distribute(nums, baskets, n):
    for num in nums:
        basket_num = (num // (10 ** n)) % 10  # int(num / 10 ** n) % 10 은 더 느리다. 
        baskets[basket_num].append(num)


def collect(nums, baskets):
    nums.clear()
    for basket in baskets:
        for _ in range(len(basket)):
            nums.append(basket.popleft())


radix_sort([34, 56, 86, 46, 13, 51, 38, 54])

클래스를 안 쓰고 코딩을 했더니 인수 부분이 길어져 깔끔하진 않습니다. 

[51, 13, 34, 54, 56, 86, 46, 38]
[13, 34, 38, 46, 51, 54, 56, 86]

 

'//'와 'int'의 실행 시간을 측정해 보았습니다.
'//'이 더 빠릅니다. 10배가량 차이가 납니다.

헉 이 정도 차이일 줄은 몰랐네요.
다른 조건에선 어떻게 될지 모르겠지만... 

def time_log(original_fn):
    import time
    def wrapper_fn(*args, **kwargs):
        start_time = time.time()
        result = original_fn(*args, **kwargs)
        end_time = time.time()
        print(f"Working Time [{original_fn.__name__}]: {end_time-start_time}")
        return result
    return wrapper_fn

@time_log
def test1():
    for num in range(10000000):
        num // 10 ** 2 % 10

@time_log
def test2():
    for num in range(10000000):
        int(num / 10 ** 2) % 10

test1()
test2()
        
# Working Time [test1]: 0.010479927062988281
# Working Time [test2]: 0.11678314208984375

 

다음 반복되는 부분을 for 문으로 묶는 게 좋겠습니다.

distribute(nums, bins, 0) 
collect(nums, bins) 
display(nums) 

distribute(nums, bins, 1) 
collect(nums, bins) 
display(nums)

 

파이썬을 처음 접하면 len(str(nums[0])) 식의 코드가 좀 어색하던데요... 

from collections import deque


def radix_sort(nums):
    baskets = [deque() for _ in range(10)]
    for i in range(len(str(nums[0]))):
        distribute(nums, baskets, i)
        collect(nums, baskets)
        print(nums)


def distribute(nums, baskets, n):
    for num in nums:
        basket_num = num // 10 ** n % 10
        baskets[basket_num].append(num)


def collect(nums, baskets):
    nums.clear()
    for basket in baskets:
        for _ in range(len(basket)):
            nums.append(basket.popleft())


radix_sort([34, 56, 86, 46, 13, 51, 38, 54])

개인적으로는 조금 더 느려도
이렇게 주고받음이 명확한 코드가
깔끔해 보입니다만... 

from collections import deque


def radix_sort2(nums):
    num_length = len(str(nums[0]))
    for i in range(num_length):
        baskets = distribute2(nums, i)
        nums = collect2(baskets)
        # print(nums)
    return nums


def distribute2(nums, n):
    baskets = [deque() for _ in range(10)]
    for num in nums:
        basket_num = (num // (10 ** n)) % 10
        baskets[basket_num].append(num)
    return baskets


def collect2(baskets):
    nums = []
    for basket in baskets:
        for _ in range(len(basket)):
            nums.append(basket.popleft())
    return nums

실제로 돌려보면 이 정도의 시간 차이가....
작다면 작고 크다면 큰... 10%에 가까운 차이...

temp = [randint(100000, 999999) for _ in range(100000)]
radix_sort(temp)
radix_sort2(temp)

Working Time [radix_sort]: 0.3390936851501465
Working Time [radix_sort2]: 0.3640251159667969

 

각 숫자의 자리가 달라도 기수 정렬이 가능하도록 한다면... 
좀 더 활용도 높은 함수가 되겠죠?

from collections import deque


def radix_sort(nums):
    num_length = len(str(max(nums)))
    nums = list(map(lambda x: f'{x:0>{num_length}}', nums))
    baskets = [deque() for _ in range(10)]
    for i in range(num_length):
        distribute(nums, baskets, num_length - i - 1)
        collect(nums, baskets)
        print(nums)
    return list(map(int, nums))


def distribute(nums, baskets, n):
    for num in nums:
        basket_num = int(num[n])
        baskets[basket_num].append(num)


def collect(nums, baskets):
    nums.clear()
    for basket in baskets:
        for _ in range(len(basket)):
            nums.append(basket.popleft())


print(radix_sort([34, 56, 86, 46, 13, 51, 38, 540]))

f문자열 포맷팅에서 {} 괄호 안에 괄호를 사용할 수 있다는 걸 우연히 발견했습니다.  
실패한 코드와 장황한 코드... 비교를 위해 남깁니다. 

nums = list(map(lambda x: f'{x:0>num_length}', nums))  # 실패
nums = list(map(lambda x: '0' * (num_length - len(x)) + x, map(str, nums)))  # 장황
nums = list(map(lambda x: f'{x:0>{num_length}}', nums))  # 성공

티스토리 코드 블럭도 {{}}를 제대로 인식하지 못하는군요.. 색이..