Kwak Jisub

정리를 미루지 말자!

새싹 AI 프로그래머
화이팅!

2 분 소요

정렬

3. 시간복잡도 \(n\)

계수 정렬

  • 계수 정렬(Counting sort)
    최대값 사이즈로 배열을 만들어 입력된 값들을 개수만큼 카운트하여 순서대로 출력
    입력데이터가 작은 범위 내에서 한정적일 경우나 입력받은 데이터를 저장하지 않을 때 사용
In [1]: 
num = [5, 2, 3, 4, 1, 2, 1]
print('최초\t:', *num)

count = [0] * (max(num) + 1)

for n in num:
    count[n] += 1
print(count)

for i in range(1, len(count)):
    count[i] += count[i-1]
print(count)

result = [0] * (len(num))
circle = 0
for n in num:
    circle += 1
    idx = count[n]
    result[idx-1] = n
    count[n] -= 1
    print(f'{circle}번째\t:', *result)
print('최종\t:', *result)
Out [1]: 
최초	: 5 2 3 4 1 2 1
[0, 2, 2, 1, 1, 1]
[0, 2, 4, 5, 6, 7]
1번째	: 0 0 0 0 0 0 5
2번째	: 0 0 0 2 0 0 5
3번째	: 0 0 0 2 3 0 5
4번째	: 0 0 0 2 3 4 5
5번째	: 0 1 0 2 3 4 5
6번째	: 0 1 2 2 3 4 5
7번째	: 1 1 2 2 3 4 5
최종	: 1 1 2 2 3 4 5
In [2]: 
# dictionary 이용: 리소스 줄이기
num = [5, 2, 3, 4, 1, 2, 1]
print('최초\t:', *num)

count = {}
for n in num:
    if count.get(n):
        # if n in count: 전체 dictionary를 순회하므로 O(N)의 시간이 걸림
        # if count.get(n): key에 따른 value return. 없으면 None(False)를 return. O(1)의 시간이 걸림
        count[n] += 1
    else:
        count[n] = 1
print(count)

result = []

for n in range(max(num) + 1):
    while count.get(n) and count[n] != 0:
        result.append(n)
        count[n] -= 1
    print(f'{n}채우기\t:', *result)
print('최종\t:', *result)
Out [2]: 
최초	: 5 2 3 4 1 2 1
{5: 1, 2: 2, 3: 1, 4: 1, 1: 2}
0채우기	:
1채우기	: 1 1
2채우기	: 1 1 2 2
3채우기	: 1 1 2 2 3
4채우기	: 1 1 2 2 3 4
5채우기	: 1 1 2 2 3 4 5
최종	: 1 1 2 2 3 4 5

기수 정렬

  • 기수 정렬(Radix sort)
    주어진 수 들간의 비교를 하지 않고 버킷을 사용해 정렬하는 방법
    낮은 자리(1의 자리)에서 높은 자리(\(10^n\) 자리) 순으로 버킷에 넣는 방법으로 정렬
    0~9까지의 버킷이 있고 이 버킷에 숫자를 넣어가며 분류
In [3]: 
num = [5, 2, 3, 4, 1, 2, 10]
buckets = [[] for _ in range(10)]

max_val = max(num)
max_digit = len(str(max_val))
result = num
digit = 1 # 자릿수

print('최초\t\t\t:', *num)
while max_val >= digit:
    while result:
        n = result.pop(0)
        buckets[(n // digit) % 10].append(n) # 각 자릿수에 따라 bucket에 n을 넣음
    
    # bucket에 담긴 순서대로 queue에 정렬
    for bucket in buckets:
        while bucket:
            result.append(bucket.pop(0))
    print(f'{digit:4d}의 자릿수 정렬\t:', *list(result))
    digit*= 10 # 자릿수 증가
    
print('최종\t\t\t:', *result)
Out [3]: 
최초			: 5 2 3 4 1 2 10
   1의 자릿수 정렬	: 10 1 2 2 3 4 5
  10의 자릿수 정렬	: 1 2 2 3 4 5 10
최종			: 1 2 2 3 4 5 10
In [4]: 
# deque의 popleft는 시간복잡도가 O(1)이다. (일반 list의 pop은 O(n))
from collections import deque

num = [5, 2, 3, 4, 1, 2, 10]
buckets = [deque() for _ in range(10)]

max_val = max(num)
max_digit = len(str(max_val))
result = deque(num)
digit = 1 # 자릿수

print('최초\t\t\t:', *num)
while max_val >= digit:
    while result:
        n = result.popleft()
        buckets[(n // digit) % 10].append(n) # 각 자릿수에 따라 bucket에 n을 넣음
    
    # bucket에 담긴 순서대로 queue에 정렬
    for bucket in buckets:
        while bucket:
            result.append(bucket.popleft())
    print(f'{digit:4d}의 자릿수 정렬\t:', *list(result))
    digit*= 10 # 자릿수 증가
    
print('최종\t\t\t:', *result)
Out [4]: 
최초			: 5 2 3 4 1 2 10
   1의 자릿수 정렬	: 10 1 2 2 3 4 5
  10의 자릿수 정렬	: 1 2 2 3 4 5 10
최종			: 1 2 2 3 4 5 10

Reference

댓글남기기

참고