7. Sorting (3)

Sorting (3)

비교 기반 정렬(comparison-based sorting)이 아닌, 값 자체를 기준으로 분류하는 정렬(non-comparison sorting)로,

입력 데이터의 특성(범위, 분포 등)을 잘 활용하면 매우 빠른 성능을 낼 수 있음.

---

 

1. Counting Sort (계수 정렬)

원소가 가질 수 있는 키 값의 범위가 작고 정수일 때,

각 키의 등장 횟수를 세어 누적합을 이용해 위치를 결정하는 방식. 추가 배열을 써서 안정적으로 정렬함.

 == 말 그대로 각 숫자가 몇 번 등장하는지 세는 방식으로 정렬

 == 비교 없이 “빈도수(count)”를 기반으로 정렬 순서를 정하는 알고리즘.

 

적용 조건

• 키가 정수여야 함.
• 키 범위 k 가 현실적으로 작아야 (예: k = O(n) 또는 작음).
• 음수 키도 처리 가능(오프셋 적용).

 

과정 (예: [4,2,2,8,3,3,1], 키 범위 1..8)

1. 카운트 배열 C[1..8] 초기화 (0).
2. 각 값 등장 횟수 누적: C[1]=1, C[2]=2, C[3]=2, C[4]=1, C[8]=1
3. 누적합으로 전환(각 인덱스까지의 총 개수): C = [1, 3, 5, 6, 6, 6, 6, 7]
4. C 배열을 누적합 형태로 변경 → C[i]는 i 이하의 원소 개수를 의미함.
5. 출력 배열 B 를 뒤에서부터 스캔(안정성 확보):
   • 값 1 → C[1]=1 → B[0]=1, C[1]--
   • 값 3 → C[3]=5 → B[4]=3, C[3]--
   • ... 최종 B = [1,2,2,3,3,4,8]

 

시간·공간 복잡도

• 시간: O(n + k)
• 공간: O(n + k) (출력 B 크기 n, 카운트 C 크기 k)
• 안정성: 안정(stable)

장단점

• 장점: 매우 빠름(키 범위 작을 때), 안정적, 구현 단순
• 단점: 키 범위 k가 크면 메모리·시간 낭비 (예: k >> n), 정수 키 한정

 

코드

CountingSort(A, B, k):
  // A: 입력[1..n], B: 출력[1..n], k: 최대 키
  C[0..k] = {0}
  for i = 1 to n:
    C[A[i]]++
  for i = 1 to k:
    C[i] = C[i] + C[i-1]
  for i = n downto 1:
    B[C[A[i]]] = A[i]
    C[A[i]]--

---

2. Radix Sort (기수 정렬)

숫자를 자리수(자릿값) 단위로 정렬(예: LSD: least-significant-digit부터).

각 단계에서 안정적인 정렬(보통 Counting Sort)을 사용하면 전체가 정렬됨.

자리수 수 d 만큼 반복하면 총 복잡도는 O(d*(n + k)).

 

• LSD (Least Significant Digit): 하위 자리부터 상위 자리로 정렬. 정수(및 고정길 문자열)에 적합.
• MSD (Most Significant Digit): 상위 자리부터 분할 정복 방식으로 진행(문자열 정렬 등).

이 있으나 LSD 위주로 정리함.

적용 조건

• 키를 고정된 자릿수(d) 로 표현 가능할 것 (예: 32-bit 정수 → d = 4 바이트 혹은 10진수 자리수)
• 각 자리값 범위 k 가 작을 것(예: 0..9 또는 0..255)

과정 (예: 3자리 10진수, 배열 [329, 457, 657, 839, 436, 720, 355])

1. LSD(1의 자리) 기준 Counting Sort → 결과 예
2. 10의 자리 기준 Counting Sort → 결과 예
3. 100의 자리 기준 Counting Sort → 최종 정렬

각 단계는 안정 정렬(Counting Sort)을 사용하므로 앞 단계에서의 정렬상태가 유지되어 최종적으로 전체 정렬 완료.

 

시간·공간 복잡도

• 시간: O(d(n + k))* (k = 기수(예: 10), d = 자리수 수)
  → 만약 d = O(1) 또는 d = log_k(MaxValue), 근사적으로 O(n) 가능
• 공간: O(n + k)
• 안정성: 안정(stable) (Counting Sort 사용

장단점

• 장점: 큰 n에 대해 정수/문자열 정렬에 매우 빠름. 비교 기반 정렬의 하한 O(n log n)을 벗어남(비교 외 정보 사용).
• 단점: 자리수(d)·기수(k)에 의존, 추가 메모리 필요, 부동소수점/가변길이 문자열은 전처리 필요.

 코드

RadixSort(A, n, d): // d = number of digits
  for i = 1 to d:
    use stable counting sort on A by digit i (digit ranges 0..k-1)

int getDigit(int x, int d) { // d = 0 for LSD (1's), 1 for tens, ...
    for (int i=0;i<d;i++) x /= 10;
    return x % 10;
}

void radixSort(int A[], int n, int d) {
    int *B = malloc(n * sizeof(int));
    for (int pos=0; pos<d; pos++) {
        // Counting sort by digit pos
        int C[10] = {0};
        for (int i=0;i<n;i++) C[getDigit(A[i], pos)]++;
        for (int i=1;i<10;i++) C[i]+=C[i-1];
        for (int i=n-1;i>=0;i--) {
            int dig = getDigit(A[i], pos);
            B[--C[dig]] = A[i];
        }
        // copy back
        for (int i=0;i<n;i++) A[i] = B[i];
    }
    free(B);
}

 

---

3. Bucket Sort (버킷 정렬)

데이터를 구간(bucket) 으로 분산시킨 뒤 각 버킷을 개별적으로 정렬(보통 삽입 정렬)하고, 버킷을 순차 결합하면 전체 정렬 완료.

데이터가 균등하게 분포되어 있을 때 매우 빠름.

 

적용 조건

• 입력 값이 어떤 구간(예: 0..1) 안에 있고 균등하게 분포되어야 효과적.
• 버킷 수 m 을 적절히(보통 n) 잡으면 각 버킷의 원소 수는 적음.

과정 (예: n=7, 배열 [0.78,0.17,0.39,0.26,0.72,0.94,0.21,0.12,0.23,0.68], 버킷 m=10)

1. 각 원소 x 를 버킷 floor(m*x) 에 넣음.
2. 각 버킷 안에서 삽입 정렬 등으로 정렬.
3. 각 버킷을 순서대로 이어 붙임 → 최종 정렬.

예시 분배:

• bucket0: 0.12
• bucket1: 0.17,0.21,0.23,0.26
• bucket6: 0.68
• bucket7: 0.72,0.78
• bucket9: 0.94
  정렬 후 합치면 오름차순.

 

시간·공간 복잡도

 

• 시간:
  • 평균: O(n + m + Σ T_bucket), 보통 m = n, 각 bucket 평균 O(1) → O(n)
  • 최악: O(n²) (모든 원소가 하나의 버킷으로 몰리면 삽입정렬 비용)
• 공간: O(n + m) (버킷에 저장)
• 안정성: 버킷 내부 정렬 방법에 의존(삽입정렬 사용 시 안정적)

 

장단점

• 장점: 균등 분포일 경우 매우 빠름(선형), 개념 직관적
• 단점: 분포 의존적, 버킷 수/분할 전략 민감, 추가 메모리 필요

 

코드

BucketSort(A, n):
  create m buckets (lists)
  for i=0 to n-1:
    idx = floor(m * A[i]) // assuming A[i] in [0,1)
    insert A[i] into bucket[idx]
  for each bucket:
    sort(bucket) // typically insertion sort for small buckets
  concatenate buckets into A

---

정리하자면,

 

정렬 알고리즘 비교

알고리즘	시간복잡도	공간복잡도	안정성	비교
Bubble Sort	O(n²)	O(1)	O	단순하지만 느림
Selection Sort	O(n²)	O(1)	X	교환 횟수 적음
Insertion Sort	O(n²)	O(1)	O	거의 정렬된 데이터에 유리
Quick Sort	O(n log n) / O(n²)	O(log n)	X	평균적으론 가장 빠름
Merge Sort	O(n log n)	O(n)	O	안정적, 분할 정복, 추가 공간 필요
Heap Sort	O(n log n)	O(1)	X	메모리 효율적
Counting Sort	O(n + k)	O(n + k)	O	정수 범위 제한, 범위 작을 때 매우 빠름
Bucket Sort	O(n + k)	O(n + k)	O	분포 의존적 == 균등 분포일 때 효과적
Radix Sort	O(d(n + k))	O(n + k)	O	자릿수 기반, 정수 정렬 최적

 

 

정렬 알고리즘 선택 가이드

상황	추천 알고리즘	이유
데이터가 거의 정렬되어 있음	Insertion Sort	O(n)에 근접, 단순
데이터 개수가 적음 (n < 20)	Insertion / Selection Sort	오버헤드 작음
일반적인 대량 데이터	Quick Sort	평균적으로 가장 빠름
안정 정렬이 필요함	Merge Sort / Counting Sort	순서 보존
메모리 제약이 심함	Heap Sort	추가 메모리 거의 없음
정수 범위가 작고 한정적	Counting Sort	O(n + k)으로 매우 빠름
데이터가 균등하게 분포된 실수형	Bucket Sort	평균 O(n)
자릿수 기반 정렬(학번, 주민번호 등)	Radix Sort	O(n)에 가까운 성능
실시간 처리 / 온라인 정렬	Insertion Sort	새 원소 추가 시 유리