우리는 지금까지 몇 가지 정렬 알고리즘을 살펴봤다.
Insertion Sort(삽입 정렬)과 Quick Sort(퀵 정렬)의 최악의 경우는 Θ()
Merge Sort(병합 정렬)의 최악의 경우 시간복잡도는 Θ()
이 알고리즘들의 공통점은 "비교(comparison)"을 통해 정렬을 수행한다는 점이다.
즉, 정렬된 순서를 알아내기 위한 유일한 방법은 두 원소를 비교하는 것뿐이다.
그리고 우리는 비교기반 알고리즘은 Ω(nlogn), 즉 최소 시간은 필요하다는 것을 알 수 있다.
근데 과연 정말 모든 비교 기반 알고리즘의 시간복잡도가 Ω(nlogn)일까?
어떤 정렬 알고리즘이 입력을 정렬할 때 어떤 비교를 어떤 순서로 하는지를 나타내는 결정트리로 증명해보자
이 구조를 통해 다음 사실을 알 수 있다
정렬할 n개의 원소가 있으면 가능한 순열은 n!개이다.
우리는 최소한 모든 가능한 정렬 결과(즉, n개의 원소에 대한 n!가지 순열)를 커버해야 한다
따라서 결정 트리는 최소한 n!개의 리프 노드를 가져야 한다.
이때 완전 이진 트리가 가장 효율적(최소 높이)인데, 이 트리의 높이는 leaf 수가 L일 때 log₂(L)이다
우리는 L = n!이니까, 트리의 최소 깊이는 log(n!)가 된다
- 비교는 YES/NO 2가지 결과 → 트리의 높이 h이면 최대 2^h개의 리프 생성 가능
즉, → nlogn
따라서 우린 모든 비교 기반 알고리즘의 최소한의 시간복잡도가 임을 알 수 있다!
Can We Do Better?
Ω()$ ... 과연 이것이 최선일까?
확실히 Merge Sort는 비교 기반 정렬 알고리즘 중에서 Optimal(최적)이다.
하지만 인간의 욕심은 끝이 없듯이, 우리는 조금 더 나은 알고리즘을 원한다.
❓ 선형 시간 정렬(linear-time sorting)은 말도 안 되는 소리일까?
조금 더 욕심을 내서 linear-time안에 끝나는 정렬은 과연 진짜 개소리일까?
놀랍게도, 가능하다!
엄밀하게 말하자면, 입력값에 대한 조건(가정)을 정해주면 최악의 경우에도 O(n) 시간에 정렬할 수 있다.
이제부터 비교 기반 정렬 알고리즘을 넘어서는 3가지의 Non-Comparison 정렬에 대해 알아보자.
Counting Sort
가장 먼저 카운팅 정렬에 대해 배워보자.
✅ 카운팅 정렬의 전제 조건 (Assumption)
입력 배열 A는 n개의 원소를 가지며, 각 원소는 0부터 k 사이의 정수이다.
✅ 핵심 직관 (Intuition)
어떤 숫자 k가 정렬 후 어느 자리에 들어가야 하는지 알기 위해,
k보다 작은 값들이 몇 개인지를 카운팅한다!
🔸 예: k = 5인 원소가 3번째로 작다면, 정렬 후 인덱스 3에 들어간다는 뜻
✅ 의사 코드
COUNTING-SORT(A, B, k): // A: 입력 배열, B: 출력 배열, k: 입력 값의 최댓값
let C[0..k] be a new array // 0부터 k까지 값을 세기 위한 보조 배열 C 선언
for i = 0 to k: // 0부터 k까지 모든 C[i]를
C[i] = 0 // 0으로 초기화 (아직 아무 숫자도 안 세었으니까)
for j = 1 to A.length: // A 배열을 한 번 순회하면서
C[A[j]] = C[A[j]] + 1 // 각 값 A[j]가 등장할 때마다 C[A[j]]를 1 증가시킴
// → C[i]는 i라는 숫자가 몇 번 나왔는지 의미
for i = 1 to k: // 누적합을 계산함
C[i] = C[i] + C[i-1] // C[i]는 이제 i 이하의 값이 몇 개인지를 나타냄
// → 즉 A[j]가 정렬 후 어디로 가야할지를 알려줌
for j = A.length downto 1: // A를 뒤에서부터 순회하면서 (안정성 유지 위함)
B[C[A[j]]] = A[j] // A[j]를 정렬된 배열 B의 정확한 위치에 넣는다
C[A[j]] = C[A[j]] - 1 // 같은 값이 또 있을 수 있으므로 위치 하나 줄여둠
🔸 Example of Counting Sort
1. 우리는 정렬이 되지 않은 배열 A의 원소는 0부터 k 사이의 정수임을 가정한다.
2. 그렇다면 k+1의 크기를 가진 카운팅용 배열 C를 세팅한다.
3. A의 원소를 하나하나 방문하며 정수 A[j]이 나올때마다, C[A[j]]를 1 씩 더해준다.
4. 그 다음, 누적합을 계산하면, C[i]는 이제 i 이하의 값이 몇 개인지를 나타냄
5. A를 뒤에서부터 순회하면서 A[j]를 정렬된 배열 B의 정확한 위치에 넣는다.
이 과정은 안정성 유지를 위해서이며, 같은 값이 또 있을 수 있으므로 위치가 하나 줄어든다.
👷🏻♂️ What is Stable?
방금 전에 언급한 안정성이란 무엇일까?
Stable sort(안정 정렬)이란 같은 값을 가진 요소들의 상대적 순서가 유지되는 정렬 방식이다
그림처럼 같은 값 3이 들어올 때도 처음 온 3이 먼저, 다음 3이 그 다음에 들어간다 → 순서 보존됨
Runtime of Counting Sort
Counting Sort의 실행시간은 매우 간단하다.
이중 반복문이 존재하지않기에 최악의 경우에도 시간복잡도가 Θ(n + k) 이다.
입력 범위 k는 입력크기 n보다 크지않으므로, 전체 알고리즘의 시간복잡도도 O(n)으로 선형이다
Radix Sort
그 다음 알아볼 정렬은 Radix(기수) 정렬이다.
말 타는 기수 아니고, 여기서의 기수(radix)는 수의 "진법(base)"을 구성하는 기본 단위를 말한다.
Radix Sort는 숫자를 각 자리(digit)로 나눠서 정렬하는데,
그 한 자리에서 표현할 수 있는 값의 개수를 기수(radix)라고 부른다는 것!
아무튼 기수 정렬의 핵심 개념에 대해 알아보자.
✅ Assumption (전제 조건)
Radix Sort는 n개의 d자리 숫자를 정렬한다.
즉, 입력 배열 A는 n개의 수로 이루어져 있고 각각의 수는 최대 d자리를 가진다 (예: 3자리 수면 d=3)
✅ Intuition (직관)
각 자리수마다 정렬을 한다.
이때는 반드시 stable sort (안정 정렬)를 사용해야 한다. (Ex. Counting Sort)
이때, 숫자를 가장 하위 자릿수부터(LSB) 차례대로 정렬함.
✅ 의사 코드
for i = 1 to d
use a stable sort to sort array A on digit i
Example of Radix Sort
가장 먼저 일의 자리수를 기준으로 안정 정렬을 실시한다.
그 다음 십의 자리수를 기준으로 안정 정렬을 실시한다.
마지막으로 백의 자리수를 기준으로 안정 정렬을 실시한다.
Runtime of Radix Sort
기수정렬은 d자리 수를 정렬한다고 가정했을 때, 맨 오른쪽 자리부터 왼쪽까지 d번 반복하면서,
각 자리별로 Counting Sort와 같은 안정 정렬(stable sort)을 적용한다.
📌 시간복잡도 분석
1. Counting Sort의 시간복잡도
Counting Sort의 시간복잡도는 Θ(n + k) 이다.
n= 원소 수k= 각 자릿수에 들어갈 수 있는 가능한 값의 개수 (예: 0~9 → k = 10)
2. Radix Sort는 d번 Counting Sort 수행
자릿수 d만큼 반복하므로 전체 시간복잡도는: Θ(d(n + k))
3. 결론 : 선형시간이 되는 경우
d= 상수 (즉, 자릿수가 고정된 경우. 예: 32비트 정수는 항상 10자리 이내)k=O(n) (각 자리 숫자의 범위가 n보다 크지 않음)
위 조건을 만족시키면 전체 시간복잡도가 다음과 같이 단순화된다.
🪣 Bucket Sort
🪣 Bucket Sort 개념 정리
✅ Assumption (전제 조건)
입력은 [0, 1] 범위에서 균등분포 (uniform distribution)로 생성된 실수들이다.
즉, 값들이 고르게 퍼져 있다고 가정해야 성능이 잘 나온다.
✅ Intuition (직관적인 아이디어)
1. [0, 1] 구간을 n개의 동일한 크기의 버킷으로 나눈다.
2. 각 입력값을 해당하는 버킷에 집어넣는다.
3. 각 버킷 안을 정렬한다.
4. 버킷들을 순서대로 이어붙이면 전체가 정렬된다.
BUCKET-SORT(A):
let B[0..n - 1] be a new array # n개의 빈 버킷 배열 B 생성
n = A.length # 입력 배열 A의 길이
for i = 0 to n - 1:
make B[i] an empty list # 각 버킷을 빈 리스트로 초기화
for i = 1 to n:
insert A[i] into list B[⌊n * A[i]⌋]
# A[i]를 [0, 1] 범위라고 가정하므로, n*A[i]를 소수점 버림 → 해당하는 버킷에 넣음
for i = 0 to n - 1:
sort list B[i] with insertion sort # 각 버킷 안은 삽입정렬로 정렬
concatenate the lists B[0], ..., B[n-1] together in order
# 버킷들을 차례로 합치면 전체 정렬된 리스트 완성
Example of Bucket Sort
Runtime of Bucket Sort
버킷 정렬의 런타임은 위와 같은데, 여기서 알 수 있듯이
버킷 생성, 분배, 병합 등은 전체 입력 n에 대해 선형 시간에 가능하다
(즉, 정렬을 제외한 나머지 과정 전부 Θ(n)이라는 것)
그러나 각 버킷은 삽입 정렬로 정렬되므로
각 버킷 B[i]의 원소 수를 라 하면 정렬 비용은 가 된다.
따라서 버킷 정렬의 총 수행시간은
“버킷 만들고 배분하는 데 걸리는 선형 시간” + “버킷마다 삽입 정렬하는 비용의 총합”
다음과 같다
그리고 이걸 기댓값 기준으로 정리하면
다음과 같다. (솔직히 이것까진 안나올 것 같다. 그냥 균등분포면 선형시간안에 끝난다만 알아두자)
지금까지의 정리 (The story so far)
길고도 길었던 Sorting 알고리즘의 대장정이 끝이났습니다.
마지막으로 지금까지 배웠던 것을 정리해봅시다.
비교 기반 정렬(Comparison-based sorting)을 사용하면, 최선의 경우라도 Ω(nlogn)따리이다.
하지만 입력값에 대한 구조적 가정(예: 작은 정수들이거나 특정한 분포를 따른다 등)을 둔다면
T(n)은 O(n)인 정렬 알고리즘도 구현 가능하다!
Nevertheless...
그럼 여러분들은 말하겠죠
아니 그럼 비교기반은 왜 배웠냐
그 이유는 비교 기반 정렬은 정밀한 데이터도 정렬할 수 있기 때문이다
사진을 예시로 보면, 이들은 소수점이 있는 실수, 지수 형태의 수, 팩토리얼, 무한소수 등 다양한 수들이다.
이 경우, 비교 정렬을 하면 π < e 같은 비교만으로 빠르게 정렬 가능하지만(가장 의미 있는 자리수만 봐도 됨)
Radix정렬 같은 경우 모든 자리수를 다 읽어야 정렬 가능하므로 정렬이 불가능합니다.
비교 기반 정렬은 Ω(nlogn)의 시간이 걸리지만, 다양한 수형에 대해 정렬이 가능하다.
선형 시간 정렬은 O(n)이 가능하긴 해도 제약 조건이 많고, 적용 가능한 상황이 제한적이다.
라고 최종적으로 정리하며
Sorting Algorithm 수업을 마치도록 하겠습니다
