알고리즘 요약
카운트정렬 (count sort)
-숫자의 발생횟수를 계산하는 누적 카운트 사용. 누적 카운트를 갱신해 순서대로 숫자를 직접배치
-작은 범위의 정수를 정렬할 때 유용. 숫자가 간격이 크면 비효율적
-시간복잡도: O(n+k)
정렬과정 설명
① ② ③ ④ ⑤ : 위치번호
[3, 2, 6, 4, 1] :숫자열이 있을 경우,
ⓞ ① ② ③ ④ ⑤ ⑥ : 배열 인덱스값
[0, 1, 1, 1, 1, 0, 1] : 카운트 배열을 만들고 숫자에 해당하는 인덱스값에 반복된 횟수 저장
-앞에서 부터 인덱스값을 결과값이라고 생각하고 1이상의 값을 출력해 주면 정렬된 목록이 된다
[1, 2, 3, 4, 6]
# 리스트를 이용한 카운트정렬
def count_sort(a):
ln = len(a) # 리스트 갯수
max_n = max(a) # 목록중 제일 큰 값
c = [0] * (max_n + 1)
# 제일 큰 숫자 길이(큰값을 인덱스로 사용하기 위해 +1)로 초기값 0으로 리스트생성
for i in range(ln): # 배열 길이 만큼 루프
c[a[i]] += 1 # 값에 해당하는 리스트 인덱스 값을 나온 횟수만큼 증가 시킴
b = [] # 소팅된 결과를 저장할 리스트 생성
for i in range(max_n + 1): # 카운트된 리스트를 루프
for j in range(c[i]): # 인덱스에 카운트 숫자 만큼 루프
b.append(i) # 결과 리스트에 인덱스값(결과값)을 추가
return b # 소팅된 결과 리턴
a = [5, 2, 3, 4, 1]
print(count_sort(a))
# 딕셔너리를 이용한 카운트정렬
# 카운트 리스트에 비해 카운트를 저장할 변수영역(메모리)를 덜 차지한다.
def count_sort_dic(a):
b = [] # 소팅된 결과를 저장할 리스트
c = {} # 숫자값에 대한 키값에 리스트를 저장할 딕셔너리
for v in a: # 목록에서 숫자를 하나씩 꺼내서
if v in c: # 키값이 있으면 기존 값 리스트에 숫자값 추가
c[v].append(v)
else: # 키값이 없으면 새로 값이 든 리스트 생성하고 추가
c[v] = [v]
for k in range(min(c), max(c) + 1): # 최소값에서 최대값 순으로 루프
if k in c: # 키값이 있으면(숫자가 있으면)
b.extend(c[k]) # 결과 목록에 추가
return b # 최종 결과 목록 리턴
a = [5, 2, 3, 4, 1]
print(count_sort_dic(a))
#include <stdio.h>
#define max_v 5 //값의 최대값을 5로 정의
void count_sort(int *a, int len) { // a:정렬할 배열 len:길이 max_v:최대값
int a_c[max_v + 1] = {0}; // 카운트용 배열. 인덱스를 값으로 사용 하기 위해 max_v+1 개의 배열 생성. 0으로 초기화.
int i, j, n = 0;
for (i = 0; i < len; i++) { // 배열길이 만큼 루프
a_c[a[i]]++; // 값에 해당하는 인덱스 배열에 +1
}
// 기존 배열에 정렬된 값으로 대입
for (i = 0; i <= max_v; i++) { // 카운트배열 길이 만큼 루프
for (j = 0; j < a_c[i]; j++) { // 각값에 카운트된 횟수만큼 값을 대입
a[n++] = i; // 인덱스 값을 값으로 대입
}
}
}
int main() { // 삽입정렬 함수 테스트
int i, a[] = {3, 2, 5, 4, 1}, len = sizeof(a) / sizeof(a[0]);
count_sort(a, len);
for (i = 0; i < len; i++) printf("%d ", a[i]); // 결과: 1 2 3 4 5
}