# ๊ณ์ ์ ๋ ฌ(Counting Sort)
# Comparison Sort
N๊ฐ ์์์ ๋ฐฐ์ด์ด ์์ ๋, ์ด๋ฅผ ๋ชจ๋ ์ ๋ ฌํ๋ ๊ฐ์ง์๋ N!์
๋ฐ๋ผ์, Comparison Sort๋ฅผ ํตํด ์๊ธฐ๋ ํธ๋ฆฌ์ ๋ง๋จ ๋ ธ๋๊ฐ N! ์ด์์ ๋ ธ๋ ๊ฐฏ์๋ฅผ ๊ฐ๊ธฐ ์ํด์๋, 2^h >= N! ๋ฅผ ๋ง์กฑํ๋ h๋ฅผ ๊ฐ์ ธ์ผ ํ๊ณ , ์ด ์์ h > O(nlgn)์ ๊ฐ์ ธ์ผ ํ๋ค. (h๋ ํธ๋ฆฌ์ ๋์ด,,, ์ฆ Comparison sort์ ์๊ฐ ๋ณต์ก๋์)
์ด๋ฐ O(nlgn)์ ์ค์ผ ์ ์๋ ๋ฐฉ๋ฒ์ Comparison์ ํ์ง ์๋ ๊ฒ
# Counting Sort ๊ณผ์
์๊ฐ ๋ณต์ก๋ : O(n + k) -> k๋ ๋ฐฐ์ด์์ ๋ฑ์ฅํ๋ ์ต๋๊ฐ
๊ณต๊ฐ ๋ณต์ก๋ : O(k) -> k๋งํผ์ ๋ฐฐ์ด์ ๋ง๋ค์ด์ผ ํจ.
Counting์ด ํ์ : ๊ฐ ์ซ์๊ฐ ๋ช ๋ฒ ๋ฑ์ฅํ๋์ง ์ผ๋ค.
# ์์ค ์ฝ๋
int arr[5]; // [5, 4, 3, 2, 1]
int sorted_arr[5];
// ๊ณผ์ 1 - counting ๋ฐฐ์ด์ ์ฌ์ด์ฆ๋ฅผ ์ต๋๊ฐ 5๊ฐ ๋ด๊ธฐ๋๋ก ํฌ๊ฒ ์ก๊ธฐ
int counting[6]; // ๋จ์ : counting ๋ฐฐ์ด์ ์ฌ์ด์ฆ์ ๋ฒ์๋ฅผ ๊ฐ๋ฅํ ๊ฐ์ ๋ฒ์๋งํผ ํฌ๊ฒ ์ก์์ผ ํ๋ฏ๋ก, ๋นํจ์จ์ ์ด ๋จ.
// ๊ณผ์ 2 - counting ๋ฐฐ์ด์ ๊ฐ์ ์ฆ๊ฐํด์ฃผ๊ธฐ.
for (int i = 0; i < arr.length; i++) {
counting[arr[i]]++;
}
// ๊ณผ์ 3 - counting ๋ฐฐ์ด์ ๋์ ํฉ์ผ๋ก ๋ง๋ค์ด์ฃผ๊ธฐ.
for (int i = 1; i < counting.length; i++) {
counting[i] += counting[i - 1];
}
// ๊ณผ์ 4 - ๋ค์์๋ถํฐ ๋ฐฐ์ด์ ๋๋ฉด์, ํด๋นํ๋ ๊ฐ์ ์ธ๋ฑ์ค์ ๊ฐ์ ๋ฃ์ด์ฃผ๊ธฐ.
for (int i = arr.length - 1; i >= 0; i--) {
counting[arr[i]]--;
sorted_arr[counting[arr[i]]] = arr[i];
}
์ฌ์ฉ : ์ ๋ ฌํ๋ ์ซ์๊ฐ ํน์ ํ ๋ฒ์ ๋ด์ ์์ ๋ ์ฌ์ฉ
(Suffix Array ๋ฅผ ์ป์ ๋, ์๊ฐ๋ณต์ก๋ O(nlgn)์ผ๋ก ์ป์ ์ ์์.)
์ฅ์ : O(n) ์ ์๊ฐ๋ณต์ก๋
๋จ์ : ๋ฐฐ์ด ์ฌ์ด์ฆ N ๋งํผ ๋ ๋, ์ฆ๊ฐ์์ผ์ฃผ๋ Counting ๋ฐฐ์ด์ ํฌ๊ธฐ๊ฐ ํผ.
(๋ฉ๋ชจ๋ฆฌ ๋ญ๋น๊ฐ ์ฌํจ)