# ๊ณ„์ˆ˜ ์ •๋ ฌ(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 < arr.length; i++) {
    counting[i] += counting[i - 1];
}
// ๊ณผ์ • 4 - ๋’ค์—์„œ๋ถ€ํ„ฐ ๋ฐฐ์—ด์„ ๋Œ๋ฉด์„œ, ํ•ด๋‹นํ•˜๋Š” ๊ฐ’์˜ ์ธ๋ฑ์Šค์— ๊ฐ’์„ ๋„ฃ์–ด์ฃผ๊ธฐ.
for (int i = arr.length - 1; i >= 0; i--) {
    sorted_arr[counting[arr[i]]] = arr[i];
    counting[arr[i]]--;
}

  • ์‚ฌ์šฉ : ์ •๋ ฌํ•˜๋Š” ์ˆซ์ž๊ฐ€ ํŠน์ •ํ•œ ๋ฒ”์œ„ ๋‚ด์— ์žˆ์„ ๋•Œ ์‚ฌ์šฉ

    (Suffix Array ๋ฅผ ์–ป์„ ๋•Œ, ์‹œ๊ฐ„๋ณต์žก๋„ O(nlgn)์œผ๋กœ ์–ป์„ ์ˆ˜ ์žˆ์Œ.)

  • ์žฅ์  : O(n) ์˜ ์‹œ๊ฐ„๋ณต์žก๋„

  • ๋‹จ์  : ๋ฐฐ์—ด ์‚ฌ์ด์ฆˆ N ๋งŒํผ ๋Œ ๋•Œ, ์ฆ๊ฐ€์‹œ์ผœ์ฃผ๋Š” Counting ๋ฐฐ์—ด์˜ ํฌ๊ธฐ๊ฐ€ ํผ.

    (๋ฉ”๋ชจ๋ฆฌ ๋‚ญ๋น„๊ฐ€ ์‹ฌํ•จ)

์ตœ์ข… ์ˆ˜์ • : 11/15/2021, 1:31:19 PM