Sep 24, 2019 โ€ข2 min read โ˜•

๐Ÿ’ป Radix Sort, ๊ธฐ์ˆ˜ ์ •๋ ฌ์ด๋ž€?

Radix sort(๊ธฐ์ˆ˜์ •๋ ฌ)์˜ ๊ธฐ๋ณธ ์•„์ด๋””์–ด๋Š” ๊ฐ๊ฐ ์ž๋ฆฌ์ˆ˜๋ผ๋ฆฌ ๋น„๊ตํ•ด์„œ ์ •๋ ฌ์„ ํ•˜๋Š” ๊ฒƒ์ด๋‹ค. ์ž๋ฆฟ์ˆ˜๋ฅผ ๋น„๊ตํ•  ๋•Œ๋Š” counting sort๋ฅผ ์‚ฌ์šฉ ํ•œ๋‹ค. Radix sort์— ๋Œ€ํ•ด ์ฐพ์•„๋ณด๋ฉด LSD์™€ MSD๊ฐ€ ์žˆ๋‹ค๋Š” ๊ฒƒ์„ ์•Œ ์ˆ˜ ์žˆ๋‹ค. LSD๋Š” ๊ฐ€์žฅ ๋‚ฎ์€ ์ž๋ฆฟ์ˆ˜๋ถ€ํ„ฐ ๋น„๊ตํ•˜๋ฉด์„œ ์ •๋ ฌ์„ ํ•˜๋Š” ๊ฒƒ์ด๊ณ , MSD๋Š” ๊ฐ€์žฅ ๋†’์€ ์ž๋ฆฟ์ˆ˜๋ถ€ํ„ฐ ๋น„๊ตํ•˜๋ฉด์„œ ์ •๋ ฌ์„ ํ•˜๋Š” ๊ฒƒ์ด๋‹ค. ์ž๋ฆฟ์ˆ˜๊ฐ€ ๊ณ ์ •๋˜์–ด์žˆ๊ธฐ ๋•Œ๋ฌธ์— stableํ•œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค.

Radix Sort๋Š” O(kn)์˜ ์‹œ๊ฐ„๋ณต์žก๋„๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ๋Š” ์ •๋ ฌ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค (k๋Š” ๊ฐ€์žฅ ํฐ ๋ฐ์ดํ„ฐ์˜ ์ž๋ฆฟ์ˆ˜์ด๋‹ค). ์ด ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ์ž‘๋™ํ•˜๋ ค๋ฉด ๋ช‡๊ฐ€์ง€์˜ ์กฐ๊ฑด๋“ค์ด ํ•„์š”ํ•˜๋‹ค:

  1. ์ˆซ์ž์ด์–ด์•ผ ํ•œ๋‹ค (ex. ["banana", "apple"] ์™€ ๊ฐ™์€ ๋ฆฌ์ŠคํŠธ๋Š” ์ •๋ ฌ ๋ถˆ๊ฐ€)
  2. ๋ถ€๋™์†Œ์ˆซ์ ์ด ์—†๋Š” ์ •์ˆ˜์—ฌ์•ผ ํ•œ๋‹ค (ex. [12.332, 29.112] ์™€ ๊ฐ™์€ ๋ฆฌ์ŠคํŠธ๋Š” ์ •๋ ฌ ๋ถˆ๊ฐ€)

์œ„์˜ ์กฐ๊ฑด๋“ค์„ ๋งŒ์กฑํ•˜์ง€ ์•Š์œผ๋ฉด Radix sort๋Š” ์‚ฌ์šฉํ•  ์ˆ˜ ์—†๋‹ค. ๊ทธ๋ฆฌ๊ณ  k์˜ ํฌ๊ธฐ๊ฐ€ ํด ์ˆ˜๋ก ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์†๋„๋„ ๋Š˜์–ด๋‚˜๊ธฐ ๋•Œ๋ฌธ์— k๊ฐ€ ์ž‘์€ ์ƒํ™ฉ์ผ์ˆ˜๋ก ๋” ๋น ๋ฅด๊ฒŒ ์ •๋ ฌ์„ ํ•  ์ˆ˜ ์žˆ๋‹ค.

๊ทธ๋ฆผ์„ ๋ณด๋ฉด ์ดํ•ด๋ฅผ ๋” ์‰ฝ๊ฒŒ ํ•  ์ˆ˜ ์žˆ๋‹ค. LSD๋ฅผ ์‚ฌ์šฉํ•ด์„œ ์ •๋ ฌ์„ ์ง„ํ–‰ํ•œ ๊ทธ๋ฆผ์ด๋‹ค.

  1. ์ฒ˜์Œ์—, ๊ฐ€์žฅ ๋‚ฎ์€ 1์˜ ์ž๋ฆฌ์ˆ˜๋“ค์„ ๋น„๊ตํ•ด์„œ ์ •๋ ฌ์„ ํ–ˆ๋‹ค. ์ด ๋•Œ ์ด ์ˆซ์ž๋“ค์„ ์ •๋ ฌํ•  ๋•Œ counting sort๋ฅผ ์‚ฌ์šฉํ•œ๋‹ค. ๊ทธ ๊ฒฐ๊ณผ 720์ด 355๋ณด๋‹ค ํผ์—๋„ 0์ด 5๋ณด๋‹ค ์ž‘๊ธฐ ๋•Œ๋ฌธ์— 720์ด ๋ฆฌ์ŠคํŠธ ์•ž์— ์˜ค๊ฒŒ ๋œ ๊ฒƒ์ด๋‹ค.
  2. ๊ทธ ๋‹ค์Œ์—๋Š” 10์˜ ์ž๋ฆฌ์ˆ˜๋“ค์„ ๋น„๊ตํ•ด์„œ ์ •๋ ฌ์„ ํ–ˆ๋‹ค. 457๊ณผ 657์„ ๋ณด๋ฉด 10์˜ ์ž๋ฆฌ์ˆ˜๊ฐ€ ์ปค์„œ ๋’ค๋กœ ๋ฐ€๋ ค๋‚˜๊ธด ํ–ˆ์ง€๋งŒ ์„œ๋กœ์˜ ์ˆœ์„œ๊ฐ€ ๋ฐ”๋€Œ์ง€ ์•Š์•˜์Œ์„ ๋ณผ ์ˆ˜ ์žˆ๋‹ค. ์ด๋Š” radix sort๊ฐ€ stableํ•œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๊ธฐ ๋•Œ๋ฌธ์— ์ด๋ ‡๊ฒŒ ๋˜๋Š” ๊ฒƒ์ด๋‹ค.
  3. ๋งˆ์ง€๋ง‰์œผ๋กœ 100์˜ ์ž๋ฆฌ์ˆ˜๋“ค์„ ๋น„๊ตํ•ด์„œ ์ •๋ ฌ์„ ํ–ˆ๋‹ค.

Python Code

class RadixSort:
    def __init__(self, num):
        self.num = num

    def radix_sort(self):
        # ์ตœ๋Œ€ digit์„ ์•Œ์•„๋ณด๊ธฐ ์œ„ํ•ด ๊ฐ€์žฅ ํฐ ์ˆ˜๋ฅผ ์ฐพ๋Š”๋‹ค
        max1 = max(self.num) 
    
        exp = 1
        while max1/exp > 0: 
            self.count_sort(self.num,exp) 
            exp *= 10


    def count_sort(self, A, k):
        B = [0] * len(A)
        C = [0] * (10) # 1์˜ ์ž๋ฆฌ, 10์˜ ์ž๋ฆฌ์ˆ˜๋งŒ ๋น„๊ตํ•˜๊ธฐ ๋•Œ๋ฌธ์— ๋ฒ”์œ„๋Š” 0~9์ด๋‹ค

        for i in range(0, len(A)): # ๊ฐ element๊ฐ€ ๋ช‡๊ฐœ์žˆ๋Š”์ง€ C์— ์ €์žฅํ•œ๋‹ค
            index = (A[i]//k) 
            C[ (index)%10 ] += 1
        
        for i in range(1,10): # C๋ฅผ ๋ˆ„์ ๊ฐ’์œผ๋กœ ๋ฐ”๊พผ๋‹ค, 0~9๊นŒ์ง€ ๋ฐ–์— ์—†๋‹ค
            C[i] += C[i-1]

        i = len(A)-1
        while i>=0:  # C ๋ฅผ indexingํ•ด์„œ ์ •๋ ฌ๋œ ๋ฆฌ์ŠคํŠธ๋ฅผ ์ฐพ๋Š”๋‹ค
            index = (A[i]//k) 
            B[ C[ (index)%10 ] - 1] = A[i] 
            C[ (index)%10 ] -= 1
            i -= 1

        # ๊ธฐ์กด ๋ฆฌ์ŠคํŠธ์— ๋ณต์‚ฌ๋ฅผ ํ•œ๋‹ค
        for i in range(len(A)): 
            A[i] = B[i]

number = [ 170, 45, 75, 90, 802, 24, 2, 66] 
print(number)
radix = RadixSort(number)
radix.radix_sort() 
print(radix.num)
ยฉ 2021 Dojin Kim, Built with Gatsby