[알고리즘] Radix Sort 기수 정렬 : 필수 기본정리 - 쉬운 원리 설명, 버켓 구현 - Kotlin

목차

기수 정렬 개념

전 포스트까지는(ex. 버블 정렬, 선택 정렬, 삽입 정렬) 정렬순서를 비교 연산을 통해 정했다면 이번 기수 정렬에서는 비교 연산을 통해 정렬 순서를 정하지 않습니다. 비교 연산을 사용하지 않기 때문에 O(dn) 빠른 속도를 가지고 있습니다. d값의 대해서는 기수 정렬 원리에서 자세히 다루겠습니다. 

 

정렬 순서를 비교연산을 쓰지 않는다면 어떤 기준으로 정렬하는 것일까요? 바로 아래처럼 자릿수를 이용하여 정렬합니다. 

기수 정렬은 가장먼저 리스트에서 가장 큰 자릿수 값을 구합니다. 그리고 1의 자리수부터 가장 큰 자릿수 값까지 정렬해 나갑니다. 설명이 부족하므로 아래 예제를 통해 기수 정렬의 원리를 알아보겠습니다.

 

기수 정렬 원리

 

Step 1 : 가장 큰 자릿수 값 구하기

[125, 383, 274, 96, 0, 9, 81, 72]

먼저 가장 큰 자릿수 값은 (125, 383, 274) 100 자릿수입니다.  

 

Step 2 : 가장 작은 1의 자리 숫자만 비교하여 정렬

[0], [81], [72], [383], [274], [125], [96], [9]

위 리스트의 1의 자리들만 비교하여 아래와같이 정렬합니다. 그러면 1의 자기 수가 가장 큰 9가 가장 뒤로 가게 됩니다.

 

Step 3: 10의 자리 숫자만 비교하여 정렬

[0, 9], [125], [72, 274], [81, 383], [96]

10의 자리수를 기준으로 정렬합니다. 0이나 9 같은 것은 10의 자릿수가 0이라고 생각하시면 됩니다. 위와 같이 10의 자릿수의 값이 같은 게 있다면 하나로 묶이게 됩니다. 

 

Step 4: 100의 자리수를 기준으로 정렬

[0, 9, 72, 81, 96], [125, 274, 383]

위와 같은 방법으로 정렬합니다.  

 

정리: 기수정렬은 O(dn) 속도를 가지고 있습니다. 여기서 d는 최대 자릿수 값입니다. 만약 100의 자릿수가 최대라면 d는 3입니다. 그래도 O(n) 속도를 가지고 있어서 빠른 속도를 가지게 됩니다.

 

기수 정렬 구현

이제 기수정렬의 원리를 알았으니 구현해봅시다. 

 

먼저 Extension함수를 사용해서 RadixSort를 가져오겠습니다. 

fun MutableList<Int>.radixSort(){
	//1 
    val base = 10
    //2
    var done = false
    var digits = 1 
    while (!done){
        done = true
    	//...more to come
    }
}

위 코드를 설명해보겠습니다. 

1. 10개의  정수를 비교하기 때문에 base를 10으로 지정합니다. (0부터 9)

2. done과 digit을 구현함으로써 코드의 프로그래스를 확인할 수 있습니다. done은 정렬이 끝났는지 알게 해 주고, digit은 어떤 자릿수를 정렬 중인지 알게 해 줍니다. 

 

하지만 위 코드만으로 정렬을 할수없습니다. While문안에 버켓을 활용하여 정렬해줘야 합니다.

 

버켓 정렬

기수 정렬을 위해 우리는 버켓 정렬을 꼭 활용해야 합니다.

버켓에는 말 그대로 버켓(바구니) 이기 때문에 여러 숫자가 들어갈 수 있게 됩니다.

각 버켓은 큐 형태를 하고 있기 때문에 우리가 정렬하는 숫자가 들어가게 됩니다.

10개의 버켓은 각 정수를 의미합니다(0부터 9)

 

예를 들어 아래 이미지에서 Queue 0 은 0 정수를 나타냅니다.

만약 지금 정렬하고 있는 게 첫 번째 자릿수라면 첫 번째 자리가 0인 

element가 Queue 0에 들어가게 됩니다. (예를 들면 10 100 40 60) 

우선 이 정도로 버켓의 특성을 마치고 아래에서 버켓을 이용하여 어떻게 정렬되는지 자세히 알아보겠습니다. 

 

아래 코드를 while문안에 넣어주세요.

 

버켓 구현

//1
val buckets = arrayListOf<MutableList<Int>>().apply{
	for(i in 0..9){
    	this.add(arrayListOf())
    }
}
//2
this.forEach{
	if(remainingPart > 0){
    	done = false
    }
    number -> 
    val remainPart = number / digits
    val digit = remainPart % base
    buckets[digit].add(number)
}
//3
digits *= base

this.clear()
this.addAll(buckets.flatten())

코드를 설명해보겠습니다. 

 1. 0부터 9 정수를 나태 내는 버켓을 만들어줍니다. 총 10개 버켓입니다. 

2. 위 이미지처럼 1의 자리 숫자 순서대로 넣어주게 됩니다.  50의 1의 자릿수는 0이기 때문에 Queue 0에 들어갑니다 64의 1의 자리 숫자는 4이기 때문에 Queue 4에 들어갑니다. 

3. 그리고 현재 자릿수를 다음 자릿수로 업데이트를 해준후 flatten() 함수를 통해 다시 리스트 형식으로 가져옵니다. 그래야 다음 자릿수를 버켓에 넣는 것을 반복하며 정렬할 수 있게 됩니다. 

flatten을 이용해 버켓에 있던 element가져오기

 4. 이렇게 반복하여  최대 자릿수까지 도달합니다.

코드를 메인 문에 실행해보겠습니다.

"radix sort" example {
   val list = arrayListOf(88, 410, 1772, 20)
   println("Original: $list")
   list.radixSort()
   println("Radix sorted: $list")
}

결과는 다음과 같습니다. 

---Example of radix sort---
Original: [88, 410, 1772, 20]
Radix sorted: [20, 88, 410, 1772]