[알고리즘] 특수한 상황에서의 빠른 정렬 - 계수, 기수 정렬

특정 상황에서 비교를 하지 않고 정렬을 함으로써 O(n) 시간 내에 정렬을 할 수 있다. 계수정렬(Counting Sort) 원소의 값이 한정적으로 0 ~ k의 자연수로 제한되어 있는 경우 사용 가능하다. 각 입력원소 x에 대해 x보다 작은 원소의 개수를 센다. 그리고 원소 x의 위치를 정한다. 예를 들어 x보다 작은 원소가 17개라면 x를 18번째 자리에 위치시킨다. 입력 배열 A와 출력을 저장할 배열 B, 임시 작업 공간 배열 C를 사용한다. ​ CountingSort(A, B, k){ vector C(k, 0); for j=1 to A.length C[A[j]]++; //C[i]는 값이 i인 원소의 개수이다. for j=1 to k C[j]+=C[j-1]; //C[i]는 이제 값이 i보다 작거나 같..

2023.08.16