알고리즘 강의 | Do it! 알고리즘 코딩테스트 with Python - 기수 정렬

04-6 기수 정렬

기수 정렬의 핵심 이론

- 값을 놓고 비교할 자릿수를 정한 다음 해당 자릿수만 비교

- 시간 복잡도: O(kn), k는 데이터의 자릿수

 

정렬 과정

10(0~9)개의 큐(버킷)을 이용, 각 큐는 값의 자릿수를 대표함

일의 자릿수를 기준으로 정렬됨

십의 자릿수를 기준으로 정렬됨

겹친 부분에서 작은 숫자가 항상 아래에 있는 이유: 그 앞 자릿수가 이미 정렬되어 있기 때문에

 

구현

def radix_sort(arr):
	# 가장 큰 수의 자릿수 구하기
	max_num = max(arr)
    max_digit = len(str(max_num))
    
    # 각 자리수를 기준으로 정렬
    for digit in range(max_digit):
    	# 0~9 숫자를 담을 임시 배열 생성
        buckets = [[] for _ in range(10)]
        
        # 입력 배열의 숫자를 각 자릿수에 맞는 버킷에 집어넣기
        for num in arr:
        	digit_val = (num // (10 ** digit)) % 10
            buckets[digit_val].append(num)
        
        # 버킷에 있는 숫자를 순서대로 꺼내고, 다시 입력 배열에 저장
        arr = [num for bucket in buckets for num in bucket]
 
 return arr

참고 사이트