-
[정렬] 기수 정렬 알고리즘Data miner/Algorithm & Data structure 2021. 3. 21. 14:11728x90
버킷 정렬(Bucket Sort)의 단점을 해소하기 위한 알고리즘이 기수 정렬 알고리즘(Radix Sort)이다. 각 자리 수에 해당하는 숫자에 정렬하고자 하는 숫자들을 차례대로 저장하는 방식이다.
이미지 출처; www.btechsmartclass.com/data_structures/radix-sort.html
Python language check !
- digit_number = *(int) (num/position)%10 : 나머지를 구한 뒤, 정수로 만들어 준다.
- for num in numbers : numbers가 빈 리스트라면, for 다음의 코드를 진행하지 않는다.
def radix(order) : is_sorted = False position = 1 while not is_sorted: is_sorted = True queue_list = [list() for _ in range(10)] for num in order: digit_number = (int) (num/position)%10 queue_list[digit_number].append(num) if is_sorted and digit_number >0: is_sorted = False index =0 for numbers in queue_list: for num in numbers: order[index] = num index +=1 position *= 10
'Data miner > Algorithm & Data structure' 카테고리의 다른 글
[자료구조] [python] [Dynamic Programming] The Coin Change Problem (1) 2022.02.08 [자료구조] [python] [Search] Cut the Tree (0) 2022.01.24 [자료구조] [python] [BFS/DFS] Shortest Reach in a Graph (0) 2021.02.25 [자료구조] [python] [BFS/DFS] Connected Cell in a Grid (0) 2021.02.24 [자료구조] [python] [heapq] Minimum Average Waiting Time (0) 2021.02.17