[Data Structure / Algorithms] Radix Sort

전성훈·2023년 11월 11일

Algorithms datastructure swift

Data Structure-Algorithm

목록 보기

22/35

주제: 기수정렬에 대해서

기수정렬이란

기수정렬은 낮은 자리수부터 비교하여 정렬한다는 것을 기본 개념으로 하는 정렬 알고리즘입니다.
기수정렬은 비교 연산을 하지 않으며 정렬 속도가 빠르지만 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요합니다.

사용 용도

정수 또는 문자열 정렬

기수 정렬은 정수나 문자열과 같이 자릿수가 있는 데이터에 적합합니다. 각 자릿수별로 데이터를 그룹화하여 정렬하기 때문입니다.

고정 길이 데이터

데이터의 길이가 일정하고 자릿수가 많지 않은 경우에 효과적입니다.

비교 기반 정렬의 대안

비교 기반 정렬 방법(예: 퀵 정렬, 병합 정렬)에 비해, 데이터의 크기가 크고, 자릿수가 많지 않을 때 더 빠를 수 있습니다.

복잡도

시간 복잡도

기수 정렬의 시간 복잡도는 일반적으로 O(nk)입니다. 여기서 n은 정렬할 요소의 수, k는 숫자의 최대 자릿수입니다.
이는 각 자릿수마다 배열의 모든 요소를 한 번씩 처리하기 때문입니다. 그러나 k가 상대적으로 작을 때, 기수 정렬은 매우 빠르게 작동할 수 있습니다.

공간 복잡도

기수 정렬의 공간 복잡도는 O(n + k) 입니다.
기수 정렬에서는 원본 배열 외에 추가적인 공간이 필요합니다. 이 추가 공간은 주로 버킷에 대한 공간이며, 이는 최대 자릿수(k)에 비례합니다.
따라서, 전체적인 공간 복잡도는 원본 배열(n)과 버킷을 위한 공간(k)을 합한 O(n + k)가 됩니다.

코드 설명

0~9 까지의 Bucket(Queue 자료구조)를 준비합니다.
모든 데이터에 대하여 가장 낮은 자리수에 해당하는 Bucket에 차례대로 데이터를 둡니다.
0부터 차례대로 버킷에서 데이터를 다시 가져옵니다.
가장 높은 자리수를 기준으로 하여 자리수를 높여가며 2번 3번 과정을 반복합니다.

extension Array where Element == Int { 
	public mutating func radixSort() { 
		let base = 10
		var done = false
		var digits = 1 
		
		while !done { 
			done = true
			var buckets: [[Int]] = .init(repeating: [], count: base)
			
			forEach { number in 
				let remainingPart = number / digits
				let digit = remainingPart % base
				buckets[digit].append(number)
				if remianingPart > 0 { 
					done = false
				}
			}
            print("\(digits): \(buckets)")

			digits *= base
			self = buckets.flatMap { $0 }
		}
	}
}

변수 초기화

base: 기수 정렬에서 사용되는 기수(10 진수)를 나타냅니다.
done: 정렬이 완료되었는지 여부를 나타내는 변수입니다.
digits: 현재 처리 중인 자릿수를 나타냅니다.

정렬 과정

while 루프는 모든 자릿수에 대해 정렬이 완료될 때까지 계속됩니다.
매 반복마다 buckets 배열이 초기화됩니다.

버킷 재배열

모든 숫자가 버킷에 할당된 후, buckets 배열을 flatMap을 사용하여 평탄화하고, 이를 원래 배열에 다시 할당합니다.

자릿수 증가

digits를 base로 곱하여 다음 자릿수로 넘어갑니다.
만약 모든 숫자가 현재 자릿수에서 0이 아니라면 done은 false로 유지되고, 다음 자릿수에 대한 정렬이 진행됩니다.

var array = [88,410,1772,20]
array.radixSort()

print()

var array2 = [4,3,2,1]
array2.radixSort()

1: [[410, 20], [], [1772], [], [], [], [], [], [88], []]
10: [[], [410], [20], [], [], [], [], [1772], [88], []]
100: [[20, 88], [], [], [], [410], [], [], [1772], [], []]
1000: [[20, 88, 410], [1772], [], [], [], [], [], [], [], []]
10000: [[20, 88, 410, 1772], [], [], [], [], [], [], [], [], []]

1: [[], [1], [2], [3], [4], [], [], [], [], []]
10: [[1, 2, 3, 4], [], [], [], [], [], [], [], [], []]