# ๊ธฐ์ ์ ๋ ฌ(Radix sort)
# Comparison Sort
N๊ฐ ์์์ ๋ฐฐ์ด์ด ์์ ๋, ์ด๋ฅผ ๋ชจ๋ ์ ๋ ฌํ๋ ๊ฐ์ง์๋ N!์
๋ฐ๋ผ์, Comparison Sort๋ฅผ ํตํด ์๊ธฐ๋ ํธ๋ฆฌ์ ๋ง๋จ ๋ ธ๋๊ฐ N! ์ด์์ ๋ ธ๋ ๊ฐฏ์๋ฅผ ๊ฐ๊ธฐ ์ํด์๋, 2^h >= N! ๋ฅผ ๋ง์กฑํ๋ h๋ฅผ ๊ฐ์ ธ์ผ ํ๊ณ , ์ด ์์ h > O(nlgn)์ ๊ฐ์ ธ์ผ ํ๋ค. (h๋ ํธ๋ฆฌ์ ๋์ด,,, ์ฆ Comparison sort์ ์๊ฐ ๋ณต์ก๋์)
์ด๋ฐ O(nlgn)์ ์ค์ผ ์ ์๋ ๋ฐฉ๋ฒ์ Comparison์ ํ์ง ์๋ ๊ฒ
# Radix sort
๋ฐ์ดํฐ๋ฅผ ๊ตฌ์ฑํ๋ ๊ธฐ๋ณธ ์์ (Radix) ๋ฅผ ์ด์ฉํ์ฌ ์ ๋ ฌ์ ์งํํ๋ ๋ฐฉ์
์ ๋ ฅ ๋ฐ์ดํฐ์ ์ต๋๊ฐ์ ๋ฐ๋ผ์ Counting Sort์ ๋นํจ์จ์ฑ์ ๊ฐ์ ํ๊ธฐ ์ํด์, Radix Sort๋ฅผ ์ฌ์ฉํ ์ ์์.
์๋ฆฟ์์ ๊ฐ ๋ณ๋ก (์) ๋์งธ ์๋ฆฌ, ์ฒซ์งธ ์๋ฆฌ) ์ ๋ ฌ์ ํ๋ฏ๋ก, ๋์ฌ ์ ์๋ ๊ฐ์ ์ต๋ ์ฌ์ด์ฆ๋ 9์ (๋ฒ์ : 0 ~ 9)
์๊ฐ ๋ณต์ก๋ : O(d * (n + b))
-> d๋ ์ ๋ ฌํ ์ซ์์ ์๋ฆฟ์, b๋ 10 (k์ ๊ฐ์ผ๋ 10์ผ๋ก ๊ณ ์ ๋์ด ์๋ค.)
( Counting Sort์ ๊ฒฝ์ฐ : O(n + k) ๋ก ๋ฐฐ์ด์ ์ต๋๊ฐ k์ ์ํฅ์ ๋ฐ์ )
์ฅ์ : ๋ฌธ์์ด, ์ ์ ์ ๋ ฌ ๊ฐ๋ฅ
๋จ์ : ์๋ฆฟ์๊ฐ ์๋ ๊ฒ์ ์ ๋ ฌํ ์ ์์. (๋ถ๋ ์์ซ์ )
์ค๊ฐ ๊ฒฐ๊ณผ๋ฅผ ์ ์ฅํ bucket ๊ณต๊ฐ์ด ํ์ํจ.
# ์์ค ์ฝ๋
void countSort(int arr[], int n, int exp) {
int buffer[n];
int i, count[10] = {0};
// exp์ ์๋ฆฟ์์ ํด๋นํ๋ count ์ฆ๊ฐ
for (i = 0; i < n; i++){
count[(arr[i] / exp) % 10]++;
}
// ๋์ ํฉ ๊ตฌํ๊ธฐ
for (i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
// ์ผ๋ฐ์ ์ธ Counting sort ๊ณผ์
for (i = n - 1; i >= 0; i--) {
buffer[count[(arr[i]/exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
for (i = 0; i < n; i++){
arr[i] = buffer[i];
}
}
void radixsort(int arr[], int n) {
// ์ต๋๊ฐ ์๋ฆฌ๋งํผ ๋๊ธฐ
int m = getMax(arr, n);
// ์ต๋๊ฐ์ ๋๋ด์ ๋, 0์ด ๋์ค๋ฉด ๋ชจ๋ ์ซ์๊ฐ exp์ ์๋
for (int exp = 1; m / exp > 0; exp *= 10) {
countSort(arr, n, exp);
}
}
int main() {
int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
int n = sizeof(arr) / sizeof(arr[0]); // ์ข์ ์ต๊ด
radixsort(arr, n);
for (int i = 0; i < n; i++){
cout << arr[i] << " ";
}
return 0;
}
# ์ง๋ฌธ
Q1) ์ ๋ฎ์ ์๋ฆฌ์๋ถํฐ ์ ๋ ฌ์ ํฉ๋๊น?
MSD (Most-Significant-Digit) ๊ณผ LSD (Least-Significant-Digit)์ ๋น๊ตํ๋ผ๋ ์ง๋ฌธ
MSD๋ ๊ฐ์ฅ ํฐ ์๋ฆฌ์๋ถํฐ Counting sort ํ๋ ๊ฒ์ ์๋ฏธํ๊ณ , LSD๋ ๊ฐ์ฅ ๋ฎ์ ์๋ฆฌ์๋ถํฐ Counting sort ํ๋ ๊ฒ์ ์๋ฏธํจ. (์ฆ, ๋ ๋ค ํ ์ ์์)
- LSD์ ๊ฒฝ์ฐ 1600000 ๊ณผ 1์ ๋น๊ตํ ๋, Digit์ ๊ฐฏ์๋งํผ ๋ฐ์ ธ์ผํ๋ ๋จ์ ์ด ์์. ๊ทธ์ ๋ฐํด MSD๋ ๋ง์ง๋ง ์๋ฆฌ์๊น์ง ํ์ธํด ๋ณผ ํ์๊ฐ ์์.
- LSD๋ ์ค๊ฐ์ ์ ๋ ฌ ๊ฒฐ๊ณผ๋ฅผ ์ ์ ์์. (์) 10004์ 70002์ ๋น๊ต) ๋ฐ๋ฉด, MSD๋ ์ค๊ฐ์ ์ค์ํ ์ซ์๋ฅผ ์ ์ ์์. ๋ฐ๋ผ์ ์๊ฐ์ ์ค์ผ ์ ์์. ๊ทธ๋ฌ๋, ์ ๋ ฌ์ด ๋์๋์ง ํ์ธํ๋ ๊ณผ์ ์ด ํ์ํ๊ณ , ์ด ๋๋ฌธ์ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ๋ ์ฌ์ฉ
- LSD๋ ์๊ณ ๋ฆฌ์ฆ์ด ์ผ๊ด๋จ (Branch Free algorithm) ๊ทธ๋ฌ๋ MSD๋ ์ผ๊ด๋์ง ๋ชปํจ. --> ๋ฐ๋ผ์ Radix sort๋ ์ฃผ๋ก LSD๋ฅผ ์ธ๊ธํจ.
- LSD๋ ์๋ฆฟ์๊ฐ ์ ํด์ง ๊ฒฝ์ฐ ์ข ๋ ๋น ๋ฅผ ์ ์์.