Counting Sort
각 숫자가 나온 횟수를 저장하고 그 횟수만큼 배열에 넣어주면 된다.
간단하다는 장점이 있지만 메모리 제한이 512mb라고 해도 int기준으로 1.2억인 배열밖에 잡을 수 없기 때문에 이렇게 크기가 큰 배열에는 카운팅 소트를 써먹을 수가 없다.
수의 범위가 어느정도 한정적일 때에만 카운팅 소트를 쓸 수 있다.
테스트를 치르는 입장에서는 수의 범위가 1000만 이하일 때는 쓰고 그렇지 않을 때는 사용하지 못한다고 생각하는게 좋다.
연습문제
boj-15688 (파이썬으로 통과가 안되고 pypy로 해야 통과가 됨)
import sys
input = sys.stdin.readline
N = int(input().rstrip())
freq = [0] * 2000001
for _ in range(N):
freq[int(input().rstrip())+ 1000000]+=1
for i in range(2000001):
for _ in range(freq[i]):
print(i - 1000000)freq 배열에 값을 추가하고 답을 출력할 때 혹은 정렬을 수행할 때 총 k칸의 값을 확인해야하기 때문에 O(N+K)이다. 즉 수의 범위 k가 작을 때에는 카운팅 소트가 굉장히 효율적으로 동작한다.
수의 범위가 제한되어있다면 구현이 간단해서 활용할 여지가 있지만 반대로 수의 범위가 크면 카운팅 소트를 사용할 수 없다.
Radix Sort
자릿수를 이용해서 정렬을 수행하는 알고리즘으로 카운팅 소트를 응용한 알고리즘이라고도 생각할 수 있다.
일의 자리부터 자리수를 증가시켜나가면서 자리수에 맞춰 배열에 담아준다. 그렇게 순서대로 옮겨가다보면 자연스럽게 정렬이 되어 있다.
라딕스의 시간복잡도는 자릿수의 최대 개수가 D개라고 할 때 D번에 걸쳐서 카운팅 소트를 하는 것과 상황이 같다. 리스트의 개수를 K라고하면 시간복잡도는 O(D(N+K))이지만 보통 리스트의 개수는 N에 비해 무시가 가능할 정도로 작기 때문에 O(DN)이 된다.
라딕스 소트는 맹점이 있다. N개의 원소를 정렬할 때 한 리스트에 N개의 원소가 다 몰릴 수도 있으니 10개 리스트 전체를 N칸의 배열로 만들어야 하는데 공간의 낭비가 너무 심하다. 해결하려면 각 리스트를 동적배열 혹은 연결리스트로 사용해야한다.
내부 정렬함수를 사용할 수 없는 특수한 상황 (c++은 stl을 사용할 수 없는 경우)가 아닌 이상 머지소트, 퀵소트를 사용해서 정렬할 일은 없지만 특히 라딕스 소트는 구현을 해야하는 상황이 아예 없다.
정렬의 응용
연습문제
boj-11652
N = int(input())
numbers = sorted([int(input()) for _ in range(N)])
answer = 0
left = 0
right = 1
max_cnt = 0
while True:
while right < N and numbers[left] == numbers[right]:
right+=1
if max_cnt < right-left+1:
max_cnt = right-left+1
answer = numbers[left]
if right >= N:
break
left = right
right = left+1
print(answer)바킹독님 예제
import sys
input = sys.stdin.readline
N = int(input().rstrip())
numbers = sorted([int(input().rstrip()) for _ in range(N)])
cnt = 0
max_val = -( 1 << 62 ) - 1
max_cnt = 0
for i in range(N):
if i == 0 or numbers[i-1] == numbers[i]: cnt+=1
else:
if cnt > max_cnt:
max_cnt = cnt
max_val = numbers[i-1]
cnt = 1
if cnt > max_cnt:
max_val = numbers[N-1]
print(max_val)정렬을 하면 같은 수는 인접하게 된다는 성질을 이용해서 간단하게 수를 셀 수 있었다. 수를 세는 것을 넘어서 중복된 원소를 제거할 수도 있다. 비슷한 문제가 나왔을 때 정렬을 하는 아이디어를 떠올릴 수 있다면 좋겠다!
