• 양수 정렬 알고리즘의 하나임.
• 크기를 기준으로 갯수를 셈(Count).
  • 범위 조건이 있는 경우에 한해서 굉장히 빠른 알고리즘임. O(n)
    • ex) 5이하 자연수 데이터들을 오름차순 정렬
• 크기를 기준으로 갯수만 세주면 되기 때문에 위치를 바꿀 필요가 없음.

알고리즘

• 배열을 탐색하면서 조건을 충족한 경우 세면됨.
• 세어진 원소 배열을 출력함.

예시

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

→ [1, 3, 2, 4, 3, 2, 5, 3, 1, 2]

• 원소의 최댓값에 따라서 count역할을 하는 배열의 크기그 정해짐.
• 원소들이 들어있는 배열의 인덱스를 하나씩 확인하면서 count 배열에 누적시킴.

소스코드 - Kotlin

fun main() {
    val count = intArrayOf(0, 0, 0, 0, 0)
    val array = intArrayOf(1, 3, 2, 4, 3, 2, 5, 3, 1, 2)

    array.forEach { count[it-1]++ }

    for(i in count.indices) {
        if(count[i] != 0) {
            repeat(count[i]) {
                print(i+1)
            }
        }
    }
}

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

• 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 을 주의해서 사용.

장점

• 시간 복잡도가 일정함.
• 구현이 간단함