• 원소의 자릿수를 기준으로 차례대로 정렬하는 방식인 알고리즘임.
  • 이는 사전순으로 정렬할 수 있어야 함.
    • 문자열도 정렬이 가능.
• 기수 정렬의 원소들은 값을 직접 비교하지 않고 정렬함.
• LSD(Least Significant Digit) 방식
  • 가장 낮은 자릿수부터 시작해서 정렬
  • 안정 정렬임.
• MSD(Most Significant Digit) 방식
  • 가장 높은 자릿수부터 시작해서 정렬
  • 문자열이나 고정 길이 정수 표현 정렬에 적합함.

알고리즘

• 각 자릿수의 값에 따라서 데이터를 분랴함.
  • ex) 1의 자리 숫자 0~9까지 분류
• 분류된 데이터를 병합하여 새로운 배열을 만듦.
• 위 두 단계를 모든 자릿수에 대해 반복함.

예시

정렬되지 않은 배열로 가정하고, 오름차순으로 정렬 프로세스로 가정.

→ ****[170, 45, 75, 90, 802, 24, 2, 66]

• 1의 자리 기준으로 정렬 → 170, 90, 2, 802, 24, 45, 75, 66
• 1의 자리로 정렬된 배열로 10의 자리로 정렬 → 2, 802, 24, 45, 66, 170, 75, 90
• 10의 자리로 정렬된 배열을 100의 자리로 정렬 → [2, 24, 45, 66, 75, 90, 170, 802]

소스코드 - Kotlin

fun radixSort(arr: IntArray): IntArray {
    val max = arr.maxOrNull() ?: return arr  // 최댓값 찾기

    var place = 1 // 자릿수
    while (max / place > 0) { // 자릿수 별로 호출
        countingSortByDigit(arr, place)
        place *= 10
    }

    return arr
}

fun countingSortByDigit(arr: IntArray, place: Int) {
    val output = IntArray(arr.size)
    val count = IntArray(10)

    // 자릿수 마다 발생 횟수 기록
    for (i in arr.indices) {
        val digit = (arr[i] / place) % 10
        count[digit]++
    }

    // 누적 계수
    for (i in 1..9) {
        count[i] += count[i - 1]
    }

    // 정렬된 배열 생성
    for (i in arr.size - 1 downTo 0) {
        val digit = (arr[i] / place) % 10
        output[count[digit] - 1] = arr[i]
        count[digit]--
    }

    // 기존 배열 업데이트
    for (i in arr.indices) {
        arr[i] = output[i]
    }
}

fun main() {
    val arr = intArrayOf(170, 45, 75, 90, 802, 24, 2, 66)
    println(radixSort(arr).joinToString(", "))
}

범위 및 함수 사용시 유의사항

• indices : IntRange타입을 반환하며**,** 수신객체의 전체 범위 반환. 위 예제 에선 0..6
• until : 범위의 마지막 요소를 포함하지 않음.
  • 0..5 => 0, 1, 2, 3, 4, 5
  • 0 until 5 => 0, 1, 2, 3, 4
• numbers.size , numbers.lastIndex 을 주의해서 사용.