728x90
병합 정렬 (Merge Sort)
파이썬 구현
def merge_sort(arr):
if len(arr) == 1: return arr
mid = len(arr) // 2
left = arr[:mid]
right = arr[mid:]
left_arr = merge_sort(left)
right_arr = merge_sort(right)
return merge(left_arr, right_arr)
def merge(left, right):
i, j = 0, 0 #투포인터
sorted_arr = []
while i < len(left) and j < len(right):
if left[i] < right[j]:
sorted_arr.append(left[i])
i += 1
else:
sorted_arr.append(right[j])
j += 1
while i < len(left):
sorted_arr.append(left[i])
i += 1
while j < len(right):
sorted_arr.append(right[j])
j += 1
return sorted_arr
if __name__ == "__main__":
A = [5, 7, 1, 3, 6, 5]
print(merge_sort(A)) # [1, 3, 5, 5, 6, 7]
기수 정렬 (Radix Sort)
해당 자릿수만 비교
파이썬 구현
from collections import deque
def radix_sort(arr):
buckets = [deque() for _ in range(10)] # 0~9 큐 만들기
digit = 1 # 자릿수
max_val = max(arr)
queue = deque(arr)
while (max_val >= digit):
# 자릿수에 따라 bucket 채우기
while queue:
num = queue.popleft()
buckets[(num // digit) % 10].append(num)
# bucket 순서대로 queue에 다시 넣어주기
for bucket in buckets:
while bucket:
queue.append(bucket.popleft())
digit *= 10 # 자릿수 증가
return list(queue)
if __name__ == "__main__":
A = [5, 7, 1, 3, 6, 5]
print(radix_sort(A)) # [1, 3, 5, 5, 6, 7]
반응형
'알고리즘 > Do it! 알고리즘 코딩테스트 (파이썬)' 카테고리의 다른 글
[9일차] 05 탐색 : 05-3 이진 탐색 (1) | 2024.04.01 |
---|---|
[8일차] 05 탐색 : 05-1 깊이 우선 탐색, 05-2 넓이 우선 탐색 (0) | 2024.04.01 |
[6일차] 04 정렬 : 04-3 삽입 정렬, 04-4 퀵 정렬 (0) | 2024.04.01 |
[5일차] 04 정렬 : 04-1 버블 정렬, 04-2 선택 정렬 (0) | 2024.03.24 |
[4일차] 03 자료구조 : 03-5 스택과 큐 (0) | 2024.03.19 |