08/27 CS공부 - 정렬 알고리즘(기수정렬, 계수정렬)

1. 기수 정렬(Radix Sort)

지금까지 정렬알고리즘이 모두 비교기반 알고리즘이었다면 Radix Sort는 분포 기반 정렬알고리즘이다. 
주어진 데이터를 자릿수 별로 정렬하면서 정렬한다. 문자나 정수열을 정렬할때 유용하다. 큰 자릿수부터 정렬하는 MSD와 작은 자릿수부터 정렬하는 LSD가 있다.

MSD(Most Significant Digit)

가장 큰 자릿수부터 시작해 낮은 자릿수로 이동하며 정렬한다.
높은 자릿수에 따라 배열을 부분배열로 분할하고 각 부분배열을 다시 높은 자릿수부터 정렬한다.
문자열 정렬에 유리하다.
부분배열을 생성하므로 공간복잡도가 높아질 수 있다.
불안정정렬이다.

fun msdRadixSort(array: IntArray) {
    val max = array.maxOrNull() ?: return
    val maxDigits = max.toString().length
    msdRadixSortHelper(array, 0, array.size - 1, maxDigits)
}

fun msdRadixSortHelper(array: IntArray, low: Int, high: Int, digit: Int) {
    if (low >= high || digit <= 0) return

    val buckets = Array(10) { mutableListOf<Int>() }
    val divisor = Math.pow(10.0, (digit - 1).toDouble()).toInt()

    for (i in low..high) {
        val bucketIndex = (array[i] / divisor) % 10
        buckets[bucketIndex].add(array[i])
    }

    var index = low
    for (bucket in buckets) {
        for (num in bucket) {
            array[index++] = num
        }
    }

    var start = low
    for (bucket in buckets) {
        val bucketSize = bucket.size
        if (bucketSize > 0) {
            msdRadixSortHelper(array, start, start + bucketSize - 1, digit - 1)
        }
        start += bucketSize
    }
}

LSD(Least Significant Digit)

낮은 자릿수부터 시작해 큰 자릿수로 이동하며 정렬한다.
안정정렬이다.
주로 정수 정렬에 사용된다.
중간에 정렬결과를 확인할 수 없다.
일관된 알고리즘(Branch Free algorithm)이다.

fun lsdRadixSort(array: IntArray) {
    // 최대값을 찾아 최대 자릿수를 계산
    val max = array.maxOrNull() ?: return
    var exp = 1  // 자릿수의 위치 (1, 10, 100, ...)

    // Counting Sort를 각 자릿수에 대해 반복
    while (max / exp > 0) {
        countingSortByDigit(array, exp)
        exp *= 10
    }
}

fun countingSortByDigit(array: IntArray, exp: Int) {
    val n = array.size
    val output = IntArray(n)  // 정렬된 배열을 저장하기 위한 임시 배열
    val count = IntArray(10)  // 자릿수별 카운트 배열

    // 현재 자릿수에서 각 숫자의 빈도를 저장
    for (i in array.indices) {
        val digit = (array[i] / exp) % 10
        count[digit]++
    }

    // 누적합을 계산하여 각 숫자의 위치 결정
    for (i in 1 until 10) {
        count[i] += count[i - 1]
    }

    // 카운트 배열을 사용하여 출력 배열에 정렬된 값을 저장
    for (i in array.indices.reversed()) {
        val digit = (array[i] / exp) % 10
        output[count[digit] - 1] = array[i]
        count[digit]--
    }

    // 정렬된 배열을 원본 배열에 복사
    for (i in array.indices) {
        array[i] = output[i]
    }
}

시간 복잡도

O(d(n+k))이다. 이때 d는 정렬할 숫자의 자릿수, n은 갯수, k는 자릿수의 범위(대부분 10진수이므로 10)이다.

공간 복잡도

주어진 배열과 자릿수의 범위 크기의 버켓이 필요하므로 O(n+k)

장점

많은 경우에서 다른 일반적인 정렬 알고리즘보다 빠르다.

단점

자릿수가 없는 것은 정렬할 수 없다.(부동 소숫점)
중간 결과를 저장할 공간이 필요하다.

2. 계수 정렬(Counting Sort)

특정 범위 내의 정수를 정렬할 때 효과적인 알고리즘이다. 최댓값을 찾아서 해당 값+1의 크기를 가지는 배열을 생성, 기존 데이터의 값을 인덱스로 활용해 몇 개나 나왔는지 카운트 한 후 누적합 배열을 이용해 해당 인덱스(데이터의 값)가 몇 번째 위치에 들어가는지 확인한 후 원본 배열을 뒤에서부터 출력배열에 배치한다. 출력배열에 배치하게되면 누적합배열의 값을 1 낮추어 다음에 같은 숫자가 나올 때 올바르게 위치할 수 있게 한다.

시간 복잡도

O(n+k)이다. 이때 n은 입력배열의 크기, k는 데이터의 범위이다.

공간 복잡도

주어진 배열과 같은 크기의 출력배열(n), 데이터 범위 크기의 카운트 배열(k)이 필요하므로 O(n+k)

장점

값의 범위가 작을 수록 비교 기반 정렬 알고리즘보다 빠르다.
안정정렬이다.

단점

값의 범위가 클수록 공간복잡도가 커지고 비효율적일 수 있다.

이러한 Radix Sort의 대표적인 예시로 Counting Sort가 있다.

코틀린 코드

fun countingSort(array: IntArray): IntArray {
    // 1. 배열에서 최대값 찾기
    val max = array.maxOrNull() ?: return array

    // 2. 카운트 배열 생성 및 초기화
    val count = IntArray(max + 1)

    // 3. 카운트 배열 채우기
    for (num in array) {
        count[num]++
    }

    // 4. 누적 합 계산
    for (i in 1 until count.size) {
        count[i] += count[i - 1]
    }

    // 5. 출력 배열 생성 및 정렬된 값 채우기
    val output = IntArray(array.size)
    for (i in array.indices.reversed()) {
        val num = array[i]
        output[count[num] - 1] = num
        count[num]--
    }

    // 6. 결과 배열 반환
    return output
}