[TIL] 2026.09.16

안정 계수정렬(Stable Counting Sort)

안정 정렬(Stable Sort)은 동일한 값을 가진 요소들의 원래 순서를 유지하는 정렬 방식.
계수 정렬을 안정 정렬로서 구현하기 위해 누적 합(Cumulative Sum) 배열을 사용한다.

안정 정렬이 필요한 이유

예시 1: 학생 시험 데이터 정렬
원본 데이터: [(김철수, 85점), (이영희, 92점), (박민수, 85점), (최지원, 88점)]

기본 계수 정렬의 경우

• 85점인 김철수와 박민수의 순서 보장 XX

안정 계수 정렬의 경우

• 원본 데이터에서 김철수가 박민수보다 앞에 있으므로, 정렬 후에도 이 순서가 유지.

[4, 1, 3, 1, 2] 안정 계수 정렬

첫 번째 단계: 카운팅 배열 선언 및 개수 세기

1. 원본 배열에서 최댓값을 찾는다. 여기서는 최댓값이 4
2. 길이가 5(최댓값+1)인 카운팅 배열을 만든다.
   • counts = [0, 0, 0, 0, 0] (인덱스 0~4)
3. 원본 배열을 순회하며 각 숫자의 등장 횟수를 기록
   • 4가 나오면: counts[4]++ -> [0, 0, 0, 0, 1]
   • 1이 나오면: counts[1]++ -> [0, 1, 0, 0, 1]
   • 3이 나오면: counts[3]++ -> [0, 1, 0, 1, 1]
   • 1이 나오면: counts[1]++ -> [0, 2, 0, 1, 1]
   • 2가 나오면: counts[2]++ -> [0, 2, 1, 1, 1]

두 번째 단계: 누적 합 배열 만들기

목적: 누적 합 배열은 결과 배열에서 각 숫자가 들어갈 마지막 위치를 찾기 위함.

1. counts 배열과 같은 크기의 누적 합 배열을 선언

   • cumulative = [0, 0, 0, 0, 0] (인덱스 0~4)

2. counts 배열의 각 원소를 이전 원소들의 합과 더해 누적합 배열을 만든다.
   - cumulative[0] = counts[0] = 0

   • cumulative[1] = cumulative[0] + counts[1] = 0 + 2 = 2
   • cumulative[2] = cumulative[1] + counts[2] = 2 + 1 = 3
   • cumulative[3] = cumulative[2] + counts[3] = 3 + 1 = 4
   • cumulative[4] = cumulative[3] + counts[4] = 4 + 1 = 5

   최종적으로 cumulative = [0, 2, 3, 4, 5]가 된다.

   세 번째 단계: 결과 배열 만들기

3. 원본 배열과 같은 크기의 결과 배열을 만든다.

   • result = new int [5]

4. 원본 배열 [4, 1, 3, 1, 2]를 뒤에서부터 순화하면서 정렬을 진행한다.

• 원본 배열의 숫자가 num인 경우, (cumulative[num]-1)이 result 배열의 인덱스가 된다.
  각 숫자의 위치가 cumulative 배열의 값에서 1을 뺸 위치에 들어가는 이유:
  1) cumulative[num]는 num 이하 숫자(작거나 같은 숫자)들의 개수를 나타낸다.
  2) 따라서 (cumulative[num]-1)은 num이 정렬된 배열에서 위치해야 할 마지막 인덱스가 된다.