[알고리즘] 기수 정렬 - 같은 자릿수 끼리끼리 비교

기수정렬(Radix Sort)

• k이하의 자릿수를 가진 자연수인 경우
• 각 자릿수별로 정렬
• 숫자를 부분적으로 비교

 

기수의 기란?

기수에서 기는 기(Radix), 특정 진수를 나타낸다

10진수의 기: 0 ~ 9

2진수의 기: 0, 1

 

예시

가장 낮은 자릿수(1의 자리)를 비교

그 다음 낮은 수(10의 자리) 비교

그 다은 자릿수(100의 자리) 비교 하면서

작은수부터 적어주면 된다.

 

어디서 쓰면 좋을까?

많은 숫자로 되어있는 상용 데이터 베이스에서 유용

주민등록번호, 계좌번호, 전화번호, 인터넷 주소 등

 

 

파이썬으로 구현하면 이렇다(그저 따라해서 이해 못했지만)

def radix_sort(A):
    RADIX = 10
    maxLengh = False
    tmp, placement = -1, 1

    while not maxLengh:
        maxLengh = True
        buckets = [list() for _ in range( RADIX )]

        for i in A:
            tmp = int((i / placement) % RADIX)
            buckets[tmp].append(i)

            if maxLengh and tmp > 0:
                maxLengh = False

        a = 0
        for b in range (RADIX):
            buck = buckets[b]
            for i in buck:
                A[a] = i
                a+=1

        placement += RADIX
    return A

if __name__ == '__main__':
    A = [123, 543, 678, 987, 124, 989]
    result = radix_sort(A)
    print(result)