기수정렬, 계수정렬

기수정렬

 

출처: https://velog.io/@hoooonshub

 

 

기수 정렬은 각 자릿수(자리 수가 높은 순서부터 낮은 순서로)마다 정렬을 수행하는 방식
일반적으로 자리 수가 작고 데이터의 범위가 좁을 때 매우 효율적으로 작동

 

 

1. 자릿수별 정렬

• 가장 낮은 자릿수부터 가장 높은 자릿수까지 차례로 정렬을 진행

2. 각 자릿수를 정렬

• 각 자릿수는 계수 정렬(Counting Sort)을 이용하여 정렬

3. 자릿수 순으로 반복

• 자릿수가 다 채워질 때까지 반복하여 정렬

 

복잡도

O(d * (n + k))

 

• d
  • 최대 자릿수(데이터의 자릿수)
• n
  • 배열의 크기
• k
  • 자릿수당 가능한 값의 범위 (예: 0~9인 경우 k=10)

자릿수가 d일 때, 각 자릿수마다 계수 정렬을 사용하여 정렬을 수행하므로 O(n) 시간이 걸리고

이를 d번 반복하기 때문에 최종적으로 O(d * (n + k))의 시간이 소요

 

 

장점

• 비교 기반이 아니다
  • 비교를 하지 않기 때문에 비교 기반 정렬(예: 퀵 정렬, 병합 정렬)의 제한을 받지 않는다.
• 특정 조건에서 매우 빠르다
  • 데이터의 자릿수가 적고, 각 자릿수의 범위가 작은 경우 매우 빠르게 동작
  • 예를 들어 10진수의 경우 자릿수가 10개 이하일 때 좋다.
• 안정 정렬
  • 기수 정렬은 안정 정렬이기 때문에 동일한 값의 순서가 유지

단점

• 자릿수에 따라 성능이 결정
  • 자릿수가 많아지면 그만큼 많은 반복이 필요
• 데이터의 범위가 클 때 비효율적
  • 값의 범위가 매우 크면 계수 정렬의 성능이 떨어져 기수 정렬도 비효율적
• 메모리 사용량
  • 계수 정렬을 기반으로 하므로 추가적인 메모리 공간이 필요

 

JAVA

import java.util.Arrays;

public class RadixSort {
    // 계수 정렬 (특정 자릿수 기준)
    public static void countingSort(int[] arr, int place) {
        int size = arr.length;
        int[] output = new int[size];
        int[] count = new int[10];  // 0~9까지의 숫자 카운트 배열

        // 자릿수에 해당하는 값을 카운트
        for (int i = 0; i < size; i++) {
            int index = arr[i] / place;
            count[index % 10]++;
        }

        // 누적 합 구하기
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }

        // 출력 배열에 값을 저장 (누적합을 이용하여 적절한 위치에 배치)
        for (int i = size - 1; i >= 0; i--) {
            int index = arr[i] / place;
            output[count[index % 10] - 1] = arr[i];
            count[index % 10]--;
        }

        // 정렬된 결과를 원본 배열에 저장
        System.arraycopy(output, 0, arr, 0, size);
    }

    public static void radixSort(int[] arr) {
        // 가장 큰 값 찾기
        int maxVal = Arrays.stream(arr).max().getAsInt();

        // 자릿수별로 정렬
        for (int place = 1; maxVal / place > 0; place *= 10) {
            countingSort(arr, place);
        }
    }

    public static void main(String[] args) {
        int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
        radixSort(arr);
        System.out.println("정렬 후: " + Arrays.toString(arr));
    }
}

 

Python

def counting_sort(arr, place):
    size = len(arr)
    output = [0] * size
    count = [0] * 10  # 0~9까지의 숫자 카운트 배열

    # 자릿수에 해당하는 값을 카운트
    for i in range(size):
        index = arr[i] // place
        count[index % 10] += 1

    # 누적 합 구하기
    for i in range(1, 10):
        count[i] += count[i - 1]

    # 출력 배열에 값을 저장 (누적합을 이용하여 적절한 위치에 배치)
    i = size - 1
    while i >= 0:
        index = arr[i] // place
        output[count[index % 10] - 1] = arr[i]
        count[index % 10] -= 1
        i -= 1

    # 정렬된 결과를 원본 배열에 저장
    for i in range(size):
        arr[i] = output[i]

def radix_sort(arr):
    # 가장 큰 값 찾기
    max_val = max(arr)

    # 자릿수별로 정렬
    place = 1
    while max_val // place > 0:
        counting_sort(arr, place)
        place *= 10


arr = [170, 45, 75, 90, 802, 24, 2, 66]
radix_sort(arr)
print("정렬 후:", arr)

 

 

---

 

 

계수정렬

 

• 비교 기반 정렬이 아닌 비교하지 않고 데이터를 정렬하는 알고리즘
• 주로 정수나 범위가 제한된 데이터를 정렬할 때 사용
• 각 데이터가 특정 범위 내에 있을 때 효율적

 

 

동작 원리

1. 데이터의 범위 파악

• 먼저 주어진 배열에서 가장 큰 값과 작은 값을 찾는다.

2. 빈도 배열 생성

• 각 값이 배열에서 얼마나 등장하는지를 저장할 배열을 만든다.
• 이 배열은 각 값에 대한 빈도를 카운팅하는 역할을 한다.

3. 누적 합 배열 생성

• 빈도 배열의 각 값을 누적합으로 변경하여 각 값이 배열에서 나올 위치를 계산한다.

4. 출력 배열 생성

• 각 원소를 정렬된 순서대로 출력 배열에 배치한다.

 

복잡도

• 시간 복잡도
  • O(n + k)
    • n
      • 입력 배열의 크기
    • k
      • 데이터의 최대값 (혹은 값의 범위)

 

👉계수 정렬은 데이터의 범위가 좁을 때 매우 효율적으로 동작하지만, 데이터 범위가 매우 크다면 비효율적일 수 있다.

 

• 공간 복잡도
  • O(k) (빈도 배열을 위한 공간이 필요함)

 

장점

• 비교 기반이 아님
  • 데이터를 비교하지 않아서 비교 기반 정렬에 비해 빠를 수 있다.
• 안정 정렬
  • 같은 값이 있을 때 원래의 순서가 유지
• 시간 복잡도
  • 데이터의 범위가 작고 원소의 개수가 많지 않다면 O(n)에 가까운 성능을 보인다.

 

단점

• 범위가 크면 비효율적
  • 데이터 값의 범위가 매우 클 경우 k가 커져서 시간 복잡도가 비효율적
• 추가 메모리 필요
  • 빈도 배열을 위한 추가 메모리가 필요
• 정수 데이터에 한정적
  • 계수 정렬은 주로 정수형 데이터에 사용된다. 실수나 문자열을 정렬하려면 추가적인 변환이 필요

 

JAVA

import java.util.Arrays;

public class CountingSort {
    public static int[] countingSort(int[] arr) {
        // 배열의 최대값을 구하여 범위 결정
        int maxVal = Arrays.stream(arr).max().getAsInt();
        
        // 빈도 배열 초기화
        int[] count = new int[maxVal + 1];
        
        // 각 값의 빈도 카운팅
        for (int num : arr) {
            count[num]++;
        }
        
        // 누적합으로 변환
        for (int i = 1; i < count.length; i++) {
            count[i] += count[i - 1];
        }
        
        // 출력 배열
        int[] output = new int[arr.length];
        
        // 값들을 정렬된 위치에 배치
        for (int i = arr.length - 1; i >= 0; i--) {
            int num = arr[i];
            output[count[num] - 1] = num;
            count[num]--;
        }
        
        return output;
    }
    
    public static void main(String[] args) {
        int[] arr = {4, 2, 2, 8, 3, 3, 1};
        int[] sortedArr = countingSort(arr);
        System.out.println("정렬 후: " + Arrays.toString(sortedArr));
    }
}

 

Python

def counting_sort(arr):
    # 배열의 최대값을 구하여 범위 결정
    max_val = max(arr)
    
    # 빈도 배열 초기화
    count = [0] * (max_val + 1)
    
    # 각 값의 빈도 카운팅
    for num in arr:
        count[num] += 1
    
    # 누적합으로 변환
    for i in range(1, len(count)):
        count[i] += count[i - 1]
    
    # 출력 배열
    output = [0] * len(arr)
    
    # 값들을 정렬된 위치에 배치
    for num in reversed(arr):
        output[count[num] - 1] = num
        count[num] -= 1
    
    return output


arr = [4, 2, 2, 8, 3, 3, 1]
sorted_arr = counting_sort(arr)
print("정렬 후:", sorted_arr)

 

기수 정렬과 계수 정렬의 관계

• 기수 정렬에서 각 자릿수의 정렬에 계수 정렬을 사용
•  O(n * k) 의 시간 복잡도(n은 배열의 크기, k는 숫자의 자릿수)
• 계수 정렬은 자릿수마다 O(n + m) 의 복잡도
• 자릿수에 비례하여 시간이 증가합니다.