Sep 22, 2019 โ€ข3 min read โ˜•

๐Ÿ’ป Counting Sort, ๊ณ„์ˆ˜ ์ •๋ ฌ์ด๋ž€?

Counting Sort(๊ณ„์ˆ˜์ •๋ ฌ)์€ ์ˆซ์ž๋“ค๊ฐ„ ๋น„๊ต๋ฅผ ํ•˜์ง€ ์•Š๊ณ  ์ •๋ ฌ์„ ํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค. ์ผ์ผ์ด ๋น„๊ต๋ฅผ ํ•˜์ง€ ์•Š๊ณ  ๊ฐ ์ˆซ์ž๊ฐ€ ๋ช‡๊ฐœ์ธ์ง€ ์„ผ ๋‹ค์Œ์— ์ •๋ ฌ์„ ํ•˜๊ธฐ ๋–„๋ฌธ์— ์‹œ๊ฐ„๋ณต์žก๋„๋Š” O(n)์ด ๋‚˜์˜ค๊ฒŒ ๋œ๋‹ค. ๋‹ค๋งŒ, Counting sort๋Š” ๋ชจ๋“  ๋ฆฌ์ŠคํŠธ์— ์ ์šฉ์„ ํ•  ์ˆ˜๋Š” ์—†๊ณ , ์ผ์ •ํ•œ ์กฐ๊ฑด์„ ๋งŒ์กฑํ•˜๋Š” ๋ฆฌ์ŠคํŠธ๋“ค์—๋งŒ ํ•ด๋‹น ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์ ์šฉํ•  ์ˆ˜ ์žˆ๋‹ค. ์กฐ๊ฑด๋“ค์€ ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค:

  1. ๋ฆฌ์ŠคํŠธ ๋‚ด์˜ ๋ชจ๋“  element๋“ค์€ ์ •์ˆ˜์—ฌ์•ผ ํ•œ๋‹ค
  2. ๋ฆฌ์ŠคํŠธ ๋‚ด์˜ ๋ชจ๋“  element๋“ค์˜ ๋ฒ”์œ„๋Š” 0~k (k๋Š” ์ •์ˆ˜)์—ฌ์•ผ ํ•œ๋‹ค
  3. k=O(n)์œผ๋กœ ๋‚˜ํƒ€๋‚˜์งˆ ์ˆ˜ ์žˆ์–ด์•ผ ํ•œ๋‹ค

์ด์ œ pseudo ์ฝ”๋“œ๋ฅผ ๋ผ์ธ๋ณ„๋กœ ๋ถ„์„ํ•ด๋ณด๋ ค๊ณ  ํ•œ๋‹ค.

A๋ผ๋Š” ์ •๋ ฌ๋˜์ง€ ์•Š์€ ๋ฆฌ์ŠคํŠธ๋ฅผ ์ •๋ ฌํ•˜๊ณ ์ž ํ•œ๋‹ค.

  • ๋ผ์ธ 1~2 : C๋ผ๋Š” ๋ฆฌ์ŠคํŠธ๋ฅผ ์ƒˆ๋กœ ๋งŒ๋“œ๋Š”๋ฐ, ์ด C์˜ ๊ธธ์ด๋Š” k์ด๋‹ค. Counting sort์˜ ๋ฒ”์œ„๋Š” 0~k๊ฐ€ ๋˜์–ด์•ผ ํ•œ๋‹ค๊ณ  ํ–ˆ๊ณ , ํ˜„์žฌ ์ฃผ์–ด์ง„ ๋ฆฌ์ŠคํŠธ์—์„œ k๋Š” 5์ด๋‹ค. ๊ทธ๋ž˜์„œ 0~5, ์ด ๊ธธ์ด 6์ธ C๋ฆฌ์ŠคํŠธ๊ฐ€ ๋งŒ๋“ค์–ด์ง€๋Š” ๊ฒƒ์ด๋‹ค.
  • ๋ผ์ธ 3~4: ์ด์ œ C๋ผ๋Š” ๋ฆฌ์ŠคํŠธ์— ๊ฐ๊ฐ element๋“ค์ด ๋ช‡๊ฐœ์ธ์ง€ ์ถ”๊ฐ€๋ฅผ ํ•œ๋‹ค. ์ดˆ๊ธฐ์— C๋Š” 0์œผ๋กœ ์ดˆ๊ธฐํ™” ๋˜์žˆ๊ณ , A๋ฅผ 0๋ฒˆ์งธ index๋ถ€ํ„ฐ ๊ธธ์ด๊นŒ์ง€ ์ˆœํšŒ๋ฅผ ํ•˜๋ฉด์„œ ํ•ด๋‹น๋˜๋Š” ๊ฐ’์„ C์— 1์”ฉ ๋”ํ•ด๋‚˜๊ฐ„๋‹ค. C[A[j]] = C[A[j]] + 1 ์ด ๋ถ€๋ถ„์„ ์˜ˆ์‹œ๋กœ ์„ค๋ช…ํ•ด๋ณด์ž๋ฉด,

    1. ์ฒ˜์Œ์— A์˜ 0๋ฒˆ์งธ index ๊ฐ’์ธ 2๊ฐ€ ๋“ค์–ด์˜จ๋‹ค. A[j]๋Š” 2๊ฐ€ ๋˜๊ณ  C[A[j]]๋Š” C[2]๊ฐ€ ๋˜๋Š” ๊ฒƒ์ด๋‹ค. ๊ทธ๋Ÿฌ๋ฉด ๊ธฐ์กด C[2]์˜ ๊ฐ’์ธ 0์—๋‹ค 1์„ ๋”ํ•ด์„œ 1์ด ๋œ๋‹ค.
    2. ๊ทธ๋‹ค์Œ์— 1๋ฒˆ์งธ index์˜ ๊ฐ’์ธ 5๊ฐ€ ๋“ค์–ด์˜ค๊ณ , ์ด๋Š” C[5]์— 1์„ ๋”ํ•˜๊ฒŒ ๋œ๋‹ค.

    ...

์ด๋Ÿฐ ์‹์œผ๋กœ ์ง„ํ–‰ํ•˜๋‹ค๋ณด๋ฉด 0์ด ๋ช‡๊ฐœ์ธ์ง€, 1์ด ๋ช‡๊ฐœ์ธ์ง€...k๊ฐ€ ๋ช‡๊ฐœ์ธ์ง€ C ๋ฆฌ์ŠคํŠธ๋ฅผ ํ†ตํ•ด์„œ ์•Œ ์ˆ˜ ์žˆ๊ฒŒ ๋œ๋‹ค.

  • ๋ผ์ธ 5~6: C ๋ฆฌ์ŠคํŠธ์˜ element๋“ค์„ ๋ˆ„์ ๊ฐ’์œผ๋กœ ๋ฐ”๊พผ๋‹ค. 0๋ฒˆ์งธ index๋Š” ๊ทธ๋Œ€๋กœ ๋‘๊ณ , 1๋ฒˆ์งธ index๋Š” ์ด์ „๊ฐ’์— ์ž์‹ ์˜ ๊ฐ’์„ ๋”ํ•œ๋‹ค 2+0 = 2, 2๋ฒˆ์งธ index๋„ ์ด์ „ ๊ฐ’์— ์ž์‹ ์„ ๋”ํ•œ๋‹ค 2+2=4....์ด๋ ‡๊ฒŒ ๋”ํ•˜๋‹ค ๋ณด๋ฉด C์˜ ๋งจ ๋งˆ์ง€๋ง‰ element๋Š” ๋‹น์—ฐํ•˜๊ฒŒ๋„ A์˜ ๊ธธ์ด๊ฐ€ ๋œ๋‹ค.
  • ๋ผ์ธ 7~9: ๋งˆ์ง€๋ง‰ for loop์—์„œ๋Š” C๋กœ ์ •๋ ฌ๋œ B ๋ฆฌ์ŠคํŠธ๋ฅผ ๋งŒ๋“ค์–ด๋‚ธ๋‹ค. A์˜ ๊ฐ’์„ ๋ณด๊ณ  ๊ทธ ๊ฐ’์„ index ์‚ผ์•„์„œ C์˜ ๊ฐ’์„ ๋ณธ๋‹ค. C์˜ ๊ฐ’์„ index์‚ผ์•„์„œ A์˜ ๊ฐ’์„ B์— ๋„ฃ๊ณ , ๋ˆ„์  C์˜ ๊ฐ’์„ -1 ํ•ด์ค€๋‹ค. ๋ง์ด ์–ด๋ ต๊ธฐ ๋•Œ๋ฌธ์— ํ•œ ๋‹จ๊ณ„์”ฉ ์‚ดํŽด๋ณด์ž

    1. A[0]์˜ ๊ฐ’ 2๋ฅผ ๋ณด๊ฒŒ๋œ๋‹ค. ์ด ๊ฐ’์„ C์˜ index๋กœ ์‚ฌ์šฉํ•œ๋‹ค C[2].
    2. C[2]์˜ ๊ฐ’์€ 4์ด๊ธฐ ๋•Œ๋ฌธ์— B[4]์— A[0]์˜ ๊ฐ’์ธ 2๋ฅผ ๋„ฃ๊ฒŒ ๋˜๋Š” ๊ฒƒ์ด๋‹ค. B[C[A[j]]] ๊ฐ€ ์ด๋Ÿฌํ•œ ์˜๋ฏธ๋ฅผ ๊ฐ€์กŒ๋‹ค. (์‹ค์ œ๋กœ๋Š” index๊ฐ€ 0๋ถ€ํ„ฐ ์‹œ์ž‘์ด๊ธฐ ๋•Œ๋ฌธ์— B[C[A[j]]-1]์„ ํ•ด์ค˜์•ผ ํ•œ๋‹ค)
    3. ๊ทธ ๋‹ค์Œ์— 2๋ฅผ ์‚ฌ์šฉํ–ˆ๊ธฐ ๋•Œ๋ฌธ์— ๋ˆ„์ ๊ฐ’์„ ํ•˜๋‚˜ ์ค„์—ฌ์ค˜์•ผ ํ•œ๋‹ค. ๊ทธ๋ž˜์„œ C[2] -= 1์„ ํ•œ๋‹ค

    loop์„ ํ•œ๋ฒˆ ๋Œ๋•Œ๋งˆ๋‹ค ์ด๋Ÿฌํ•œ ๋™์ž‘์„ ์ง„ํ–‰ํ•˜๊ฒŒ ๋˜๊ณ , A์˜ ๋งˆ์ง€๋ง‰ element๋ฅผ B์— ๋„ฃ์„ ๋•Œ๊นŒ์ง€ ์ง„ํ–‰์ด ๋œ๋‹ค.

Timeย Complexityย &ย inplace,ย stableย ์—ฌ๋ถ€

  • ๋ผ์ธ 1~2๋Š” 0~k์ด๊ธฐ ๋•Œ๋ฌธ์— O(k)์ด๋‹ค
  • ๋ผ์ธ 3~4๋Š” n๊นŒ์ง€์—ฌ์„œ O(n)์ด๋‹ค
  • ๋ผ์ธ 5~6์€ k๊นŒ์ง€์—ฌ์„œ O(k)์ด๋‹ค
  • ๋ผ์ธ 7~9๋Š” n๊นŒ์ง€์—ฌ์„œ O(n)์ด๋‹ค

์‹œ๊ฐ„๋ณต์žก๋„๋ฅผ ๋‹ค ๋”ํ•˜๋ฉด O(n+k)๊ฐ€ ๋œ๋‹ค. ๋งŒ์•ฝ k=O(n) ์ด๋ฉด counting sort์˜ ์‹œ๊ฐ„๋ณต์žก๋„๋Š” O(n)์ด ๋œ๋‹ค. ์ •๋ ฌ์„ ํ•˜๋Š” ๊ฒƒ์ด ์ด๋ ‡๊ฒŒ ๋น ๋ฅผ ์ˆ˜ ์žˆ๋Š” ์ด์œ ๋Š” counting sort๋Š” ๋น„๊ต๋ฅผ ํ•˜์ง€ ์•Š๊ธฐ ๋•Œ๋ฌธ์ด๋‹ค. ํ•˜์ง€๋งŒ, k์˜ ๊ฐ’์ด ๋„ˆ๋ฌด ์ปค์ง€๋ฉด ์ผ๋ฐ˜ ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜๋ณด๋‹ค ๋Š๋ ค์งˆ ์ˆ˜ ์žˆ๋Š” ๋‹จ์ ์ด ์žˆ๋‹ค.

Counting sort๋Š” ๊ธฐ์กด element๋“ค์˜ ์ˆœ์„œ๋ฅผ ์ง€ํ‚ค๋ฉด์„œ ์ •๋ ฌ์„ ์‹œํ‚ค๊ธฐ ๋•Œ๋ฌธ์— stable sort๋กœ ๋ถ„๋ฅ˜๋œ๋‹ค. ํ•˜์ง€๋งŒ, ์ถ”๊ฐ€์ ์ธ ๋ฉ”๋ชจ๋ฆฌ๋ฅผ ์š”๊ตฌํ•˜๊ธฐ ๋•Œ๋ฌธ์— in-place ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ์•„๋‹ˆ๋‹ค.

Python Code

def couting_sort(A, k):
    B = [0] * len(A)
    C = [0] * (k+1)

    for i in range(len(A)): # ๊ฐ element๊ฐ€ ๋ช‡๊ฐœ์žˆ๋Š”์ง€ C์— ์ €์žฅํ•œ๋‹ค
        C[A[i]] += 1
    
    for i in range(1,len(C)): # C๋ฅผ ๋ˆ„์ ๊ฐ’์œผ๋กœ ๋ฐ”๊พผ๋‹ค
        C[i] += C[i-1]

    for i in range(len(A)): # C๋ฅผ indexingํ•ด์„œ B์— ์ €์žฅํ•œ๋‹ค
        B[C[A[i]]-1] = A[i]
        C[A[i]] -= 1

    return B
        
counting_number = [1, 0, 3, 1, 0, 2, 5, 2, 1, 4]
print(counting_number)
count = couting_sort(counting_number, max(counting_number))
print(count)
ยฉ 2021 Dojin Kim, Built with Gatsby