지금까지는 정렬 순서를 결정하기 위해 비교에 의존해왔다.

Radix Sort 는 선형 시간안에 정렬이 가능한, non-comparative algorithm이다.

동작 방식

---

기수정렬은 자리수를 비교한다.

예시 배열 [88, 410, 1772, 20] 이 있다고 하자.

1. 1의 자리 비교

   1의 자리를 비교하면 0, 2, 8이다. → 이 순서대로 정렬하면 [410, 20, 1772, 88] 순서로 정렬된다.

2. 10의 자리 비교

   1에서 정렬된 배열에서 10의 자리를 비교하면, 1, 2, 7, 8 순서이다. 이 순서대로 정렬하면,

   [410, 20, 1772, 88] 이다. 변경된게 없으므로 다음으로 넘어간다.

3. 100의 자리 비교

   100의 자리 숫자만으로 비교하면, 4, 0, 7, 0 이다. (해당 자릿수가 없으면 0으로 취급한다)

   이를 정렬하면 0, 4, 7이고 이 순서대로 배열을 정렬하면

   [20, 88, 410, 1772] 가 된다.

1. 1000의 자리 수 비교

   1000의 자리 숫자만으로 비교하면, 0, 1 이다. 0인 경우는 20, 88, 410 이 하나의 bucket에 있고, 1의 경우는 1772 하나 뿐이다.

   같은 bucket 내에서의 정렬 순서는 앞선 단계에서 이미 정렬된 상태이다!

구현

---

extension Array where Element == Int {
	public mutating func radixSort() {
	}
}

public mutating func radixSort() {
	let base = 10
	
	var done = false // 정렬이 완료되었는지 체크 
	var digits = 1 // 
	while !done {
	}
}

Bucket Sort

for 문 안에서는 같은 bucket 안에 들어있는 숫자들을 정렬하기 위한 bucket sort 가 필요하다.

// 1. 이차원 배열로 초기화 -> 10개의 빈 배열을 가짐
// 각 자릿수별로 숫자를 그룹핑하는 역할을 함
// 1의 자릿수가 5인 숫자는 bucket[5]에 저장되겠지 
var buckets: [[Int]] = .init(repeating: [], count: base)

// 2. 
forEach { number in 
	// digits 는 현재 정렬할 자릿수 
	let remainingPart = number / digits 
	
	// remainingPart에서 base로 나눈 나머지 값. -> 이건 해당 자릿수에서의 값을 알 수 있음 
	let digit = remainingPart % base 
	
	// 계산된 자릿수에 해당하는 버킷에 숫자 추가 
	// 1의 자릿수에 3이 있다면, buckets[3]에 숫자 추가 
	buckets[digit].append(number)
}

// 3. 
// digits는 1로 시작
// 매 루프때마다 10을 곱해 점점 더 높은 자릿수로 가도록 함 
digits *= base 

// 10개의 버킷에 분류된 숫자들을 하나의 배열로 다시 합치는 작업 
// flatMap을 통해 2차원 배열을 1차원 배열로 만든다 
self = buckets.flatMap { $0 }

• 1의 자릿수를 기준으로 숫자를 분류하여 버킷에 넣고, 다시 하나의 배열로 병합.
• 10의 자릿수를 기준으로 버킷에 분류하고 다시 병합.
• 100의 자릿수... 그리고 1000의 자릿수까지 같은 방식으로 자릿수별로 정렬을 반복.
• 최종적으로 모든 자릿수에 대해 정렬이 완료되면 배열이 완전히 정렬된다!

종료 조건 세팅하기

1. done 을 루프 돌기 시작할 때 true로 설정한다.

2. forEach 문 안에서 remainingPart가 있을 때 done 을 설정하여 필요한 경우 계속 while 문을 돌 수 있도록 한다. (이 말은 남아있지 않으면 while 문을 탈출 할 수 있는 것.

   if remainingPart > 0 {
   	done = false 
   }

Complexity

---

• 평균 시간 복잡도
  • O(k x n)
    (k: 배열에서 가장 큰 자릿수, n : 배열 내 정수의 개수)
    
• 가장 효율적으로 동작하는 경우
  • 모든 숫자가 동일한 자릿수를 가질 때 → O(n)
• 공간복잡도
  • O(n) (버킷을 저장할 공간이 필요하니까)

전체 코드

public mutating func radixSort() {
    let base = 10
    
    var done = false
    var digits = 1
    while !done {
        done = true
        /* 여기서부터 bucket sort */
        var buckets: [[Int]] = .init(repeating: [], count: base)
        forEach { number in
            let remainingPart = number / digits
            let digit = remainingPart % base
            buckets[digit].append(number)
            if remainingPart > 0 {
                done = false
            }
        }
        digits *= base
        self = buckets.flatMap { $0 }
    }
}