일지
알고리즘...23
niamdank
2021. 7. 20. 15:56
계수 정렬
입력의 값이 모두 Ο(n)을 넘지 않는 경우 사용할 수 있는 정렬 방법으로 Θ(n) 이 소요되는 알고리즘이다.
계수 정렬 알고리즘
// A[]를 정렬한 결과가 B[]에 저장될 때
CountingSort(A[], B[], n)
{
// 배열(혹은 딕셔너리) C[] 초기화
for i ← 1 to k
{
C[i] ← 0;
}
// 값이 A[j]인 개수
for j ← 1 to n
{
C[A[j]]++;
}
// 값이 A[j] 보다 작은 것의 개수
for i ← 2 to k
{
C[i] ← C[i] + C[i - 1];
}
// B[]에 A[]의 자리를 확인하여 저장
for j ← n downto 1
{
B[C[A[j]]] ← A[j];
C[A[j]]--;
}
}