[Algorithm] 정렬 알고리즘 3 ~ 빗, 카운팅 정렬 ~ (Kotlin)

빗 정렬

 

https://en.wikipedia.org/wiki/Comb_sort

Comb sort - Wikipedia

빗 정렬은 비교적 간단한 정렬 알고리즘으로 쉘 정렬이 삽입 정렬을 개선하는 것과 같은 방식으로 버블 정렬을 개선하며 둘 다 의도한 위치에서 멀리 떨어진 요소들이 스왑당 1칸씩 이동할 수 있게 한다는 점에서 차이가 있다
버블 정렬에선 거북이 또는 리스트 끝 근처의 작은 값을 없애면 정렬 속도가 느려지므로 기본 아이디어는 거북이를 없애는 것이다. 리스트 시작 부분에 큰 값인 토끼는 버블 정렬에서 문제가 되지 않는다. 버블 정렬에선 두 요소를 비교할 때 항상 간격(=서로 간의 거리)이 1이다. 빗 정렬의 기본 아이디어는 간격이 1보다 훨씬 클 수 있다는 것이다. 실제 교환을 수행하는 버블 정렬의 내부 루프는 교환된 요소 사이의 간격이 축소 계수 k의 단계로 (외부 루프가 반복될 때마다) 내려가도록 수정된다. 간격은 정렬되는 리스트 n의 길이를 축소 계수 k로 나눈 값으로 시작하고 수정된 버블 정렬의 한 패스가 그 간격으로 적용된다. 그 후 간격을 다시 축소 계수로 나누고 얻은 새 간격을 써서 리스트를 정렬하며 간격이 1이 될 때까지 반복한다. 이 때 빗 정렬은 리스트가 완전 정렬될 때까지 간격 1을 써서 계속된다
따라서 정렬의 마지막 단계는 버블 정렬과 같지만 이 때는 대부분의 거북이가 처리됐으므로 버블 정렬이 효율적이다. 축소 계수는 빗 정렬의 효율성에 큰 영향을 준다. 도보시에비츠는 1.333...을 제안했고 Lacey와 Box는 길이가 1000인 20만 개 이상의 무작위 리스트에 대한 테스트 끝에 1.3을 이상적인 축소 계수로 제안했다
값이 너무 작으면 불필요하게 많은 비교를 수행해서 속도가 느려지고 너무 크면 거북이를 효과적으로 처리하지 못해서 간격이 1인 패스가 많이 필요하다. 간격이 줄어들면서 정렬 패스를 쓰는 패턴은 쉘 정렬과 유사하지만 쉘 정렬에선 배열이 다음의 가장 작은 간격으로 이동하기 전에 각 패스에서 완전 정렬된다. 빗 정렬의 패스는 요소를 완전 정렬하지 않는다...(중략)

축소 계수 k = 1.24733으로 빗 정렬

 

아래는 코틀린으로 빗 정렬을 구현한 예시다.

 

fun combSort(arr: IntArray) {
    val n = arr.size
    var gap = n
    var swapped = true

    // gap이 1이거나 교환이 더 이상 일어나지 않을 때까지 반복
    while (gap != 1 || swapped) {
        // gap을 줄임
        gap = getNextGap(gap)

        // 교환 발생 여부
        swapped = false

        // gap만큼 떨어진 요소를 비교하며 정렬
        for (i in 0 until n - gap) {
            if (arr[i] > arr[i + gap]) {
                // 두 요소를 교환
                val temp = arr[i]
                arr[i] = arr[i + gap]
                arr[i + gap] = temp
                swapped = true
            }
        }
    }
}

/* gap을 구하는 함수 */
fun getNextGap(gap: Int): Int {
    // 1.3으로 gap을 줄이면서 소수점 이하 버림
    val newGap = (gap / 1.3).toInt()
    // gap이 1보다 작으면 1로 설정
    return if (newGap < 1) 1 else newGap
}

fun main() {
    val arr = intArrayOf(64, 34, 25, 12, 22, 11, 90)
    println("정렬 전 : ${arr.joinToString()}")
    combSort(arr)
    println("정렬 후 : ${arr.joinToString()}")
}

// 정렬 전 : 64, 34, 25, 12, 22, 11, 90
// 정렬 후 : 11, 12, 22, 25, 34, 64, 90

 

위 코드의 작동 순서를 확인한다.

 

• 처음 gap은 배열 길이가 7이라 7로 설정된다
• getNextGap()에서 7 / 1.3 = 5기 때문에 gap이 5로 변경된다. 이후 인덱스 0 vs 5, 1 vs 6을 비교한다
  • 64 vs 11 : 64가 더 크기 때문에 두 값을 스왑한다 -> [11, 34, 25, 12, 22, 64, 90]
  • 34 vs 90 : 34가 더 작기 때문에 교환하지 않는다
  • 교환이 1회 발생해 swapped는 true로 설정된다
• 다시 getNextGap()이 호출되고 5 / 1.3 = 3이기 때문에 인덱스 0 vs 3, 1 vs 4, 2 vs 5를 비교한다
  • 11 vs 12 : 11이 더 작기 때문에 교환하지 않는다
  • 34 vs 22 : 34가 더 크기 때문에 두 값을 스왑한다 -> [11, 22, 25, 12, 34, 64, 90]
  • 25 vs 64 : 25가 더 작기 때문에 교환하지 않는다
  • 교환이 1회 발생해 swapped = true로 설정된다
• 다시 getNextGap()이 호출되고 3 / 1.3 = 2기 때문에 인덱스 0 vs 2, 1 vs 3, 2 vs 4를 비교한다
  • 11 vs 25 : 11이 더 작기 때문에 교환하지 않는다
  • 22 vs 12 : 22가 더 크기 때문에 두 값을 스왑한다 -> [11, 12, 25, 22, 34, 64, 90]
  • 25 vs 34 : 25가 더 작기 때문에 교환하지 않는다
  • 교환이 1회 발생해 swapped = true로 설정된다
• 다시 getNextGap()이 호출되고 2 / 1.3 = 1이기 때문에 인덱스 0 vs 1, 1 vs 2, 2 vs 3, 3 vs 4, 4 vs 5, 5 vs 6을 비교한다
• 사실상 버블 정렬처럼 인접한 두 요소끼리 비교해서 정렬한다
  • 11 vs 12 : 11이 더 작아서 교환하지 않는다
  • 12 vs 25 : 12가 더 작아서 교환하지 않는다
  • 25 vs 22 : 25가 더 커서 두 값을 스완한다 -> [11, 12, 22, 25, 34, 64, 90]
  • 다른 비교에서도 왼쪽 값이 더 작아서 교환하지 않는다
  • 교환이 1회 발생해 swapped = true로 설정된다
• 다시 nextGap()이 호출되고 1 / 1.3 = 0이다. 1보다 작아서 getNextGap()에서 1을 리턴한다
• 다시 인접한 두 요소끼리 비교해서 정렬하는데 앞서 모든 값이 정렬되어 더 이상 정렬이 발생하지 않는다
• swapped는 false고 while문 실행 조건에 맞지 않아 while문을 탈출한다 -> combSort() 종료
• 최종 결과 = [11, 12, 22, 25, 34, 64, 90]

 

카운팅 정렬

 

https://en.wikipedia.org/wiki/Counting_sort

Counting sort - Wikipedia

카운팅 정렬은 정수값인 키에 따라 객체 모음을 정렬하는 정수 정렬 알고리즘이다. 고유한 키값을 가진 객체의 수를 세고 그 수에 접두사 합계를 적용해서 출력 시퀀스에서 각 키의 위치를 결정하는 식으로 작동한다. 실행 시간은 항목 수, 최대 키 값, 최소 키 값의 차이에 따라 선형적이므로 키의 변동이 항목 수보다 크지 않은 상황에서만 직접 쓰기에 적합하다. 더 큰 키를 더 효율적으로 처리할 수 있는 다른 정렬 알고리즘인 기수 정렬의 하위 루틴으로 자주 쓰인다. 카운팅 정렬은 비교 정렬이 아니므로 키 값을 배열 인덱스로 사용하며...(중략)...이 알고리즘은 재귀, 서브루틴 호출 없이 단순 for만 사용하기 때문에 분석이 간단하다. 카운트 배열 초기화, 카운트 배열에서 접두사를 합치는 2번째 for문은 각각 최대 k+1회 반복되므로 O(k) 시간이 걸린다. 나머지 2개의 for문과 출력 배열 초기화에는 각각 O(n) 시간이 걸린다. 따라서 전체 알고리즘의 시간은 이 시간들을 합친 O(n + k)다. 길이가 k+1, n인 배열ㅇ르 쓰기 때문에 알고리즘의 총 공간 사용량도 O(n + k)다. 최대 키 값이 항목 수보다 작은 인스턴스면 입출력 배열 외에 사용하는 유일한 스토리지가 O(k)를 사용하는 카운트 배열이므로 카운팅 정렬은 매우 공간 효율적일 수 있다...(중략)...이 알고리즘은 입력에 있는 키는 1, 없는 키는 0을 저장하는 비트 벡터로 카운트 배열을 대체해서 중복 키를 없애는데도 사용할 수 있다

 

아래는 코틀린으로 카운팅 정렬을 구현한 예시다.

 

fun countingSort(arr: IntArray): IntArray {
    if (arr.isEmpty()) return arr

    val max = arr.maxOrNull() ?: return arr // 배열의 최대값
    val min = arr.minOrNull() ?: return arr // 배열의 최소값

    val countArraySize = max - min + 1
    val countArray = IntArray(countArraySize)

    // 입력 배열에서 각 숫자의 등장 횟수를 카운팅 배열에 기록
    for (num in arr) {
        countArray[num - min]++
    }

    // 카운팅 배열을 통해 원래 배열 정렬
    var index = 0
    for (i in countArray.indices) {
        while (countArray[i] > 0) {
            arr[index] = i + min
            index++
            countArray[i]--
        }
    }

    return arr
}

fun main() {
    val arr = intArrayOf(4, 2, 2, 8, 3, 3, 1)
    println("정렬 전 : ${arr.joinToString(", ")}")
    val sortedArray = countingSort(arr)
    println("정렬 후 : ${sortedArray.joinToString(", ")}")
}

// 정렬 전 : 4, 2, 2, 8, 3, 3, 1
// 정렬 후 : 1, 2, 2, 3, 3, 4, 8

 

이 코드의 동작 순서를 확인한다.

 

• 입력 배열 안에서 최대값, 최소값을 찾아서 카운팅 배열 크기를 결정한다
  • 최대값 = 8, 최소값 = 1
  • 카운팅 배열의 크기는 8 - 1 + 1 = 8이다
  • 입력 배열의 값들이 특정 범위 안에 있으며 이 범위는 최소값~최대값을 포함한다. 이 범위 안의 모든 값들의 등장 횟수를 세고, 입력 배열의 값들이 min 값보다 작은 값을 포함하는 경우 불필요하게 카운팅 배열 크기가 커질 수 있어서 max 값으로 카운팅 배열 크기를 설정하지 않는다
• 이제 입력 배열에서 각 숫자의 출현 빈도를 기록하는 카운팅 배열을 만든다. 이 배열의 각 인덱스는 입력 배열의 값에 해당하고 그 값이 몇 번 나타났는지를 말한다
• countArray = [0, 0, 0, 0, 0, 0, 0, 0]으로 초기화된 후 각 숫자의 등장 빈도를 기록
  • 4가 1번 등장 -> countArray[3] +=1 -> [0, 0, 0, 1, 0, 0, 0, 0]
  • 2가 2번 등장 -> countArray[1] += 2 -> [0, 2, 0, 1, 0, 0, 0, 0]
  • 8이 1번 등장 -> countArray[7] += 1 -> [0, 2, 0, 1, 0, 0, 0, 1]
  • 3이 2번 등장 -> countArray[2] += 2 -> [0, 2 , 2, 1, 0, 0, 0, 1]
  • 1이 1번 등장 -> countArray[0] +=1  -> [1, 2, 2, 1, 0, 0, 0, 1]
• 이제 카운팅 배열을 순회하면서 각 숫자의 등장 횟수만큼 원래 배열에 값을 다시 채운다. 각 값의 등장 횟수가 0보다 클 때 원래 배열에 값을 넣고 등장 횟수를 줄인다
• 원래 배열에 값을 채우기 때문에 리턴될 배열의 총 길이는 7이다 
  • countArray[0]은 1이다 -> 배열에 1을 넣는다 -> [1, _, _, _, _, _, _]
  • countArray[1]은 2다 -> 배열에 2를 2번 넣는다 -> [1, 2, 2, _, _, _, _]
  • countArray[2]는 2다 -> 배열에 3을 2번 넣는다 -> [1, 2, 2, 3, 3, _, _]
  • countArray[3]은 1이다 -> 배열에 4를 1번 넣는다 -> [1, 2, 2, 3, 3, 4, _]
  • countArray[7]은 1이다 -> 배열에 8을 1번 넣는다 -> [1, 2, 2, 3, 3, 4, 8]
• 최종 결과 = [1, 2, 2, 3, 3, 4, 8]

 

카운팅 배열 크기를 설정할 때 최대값으로만 설정하면 안된다. 만약 최대값이 10만을 넘어가는 숫자라면 생성되는 배열의 크기도 10만이 되어 메모리 이슈가 발생한다. 그래서 최대값에서 최소값을 빼는 처리가 필요하다.

이후에 1을 더하는 건 입력 배열의 값들은 어떤 범위 안에 들어 있으며, 이 범위는 최소값~최대값을 모두 포함한다. max - min을 계산하면 8 - 1 = 7이 되는데, 이 값은 최대값(8) 자신을 포함하지 않는 크기다. 그래서 1을 더해야 한다.

 

배열 안에서 최대값, 최소값을 찾아서 카운팅 배열의 크기를 결정한 후 -> 입력 배열에서 각 숫자의 출현 빈도를 카운팅 배열에 기록하고 -> 완성된 카운팅 배열을 기반으로 원래 배열에 숫자들을 순서대로 넣어서 정렬하는 식으로 작동하는 게 카운팅 정렬이다. 이 정렬은 입력 값의 범위가 제한된 정수일 때 효율적으로 작동한다.