Python 기수정렬 구현

1 개요[ | ]

Python 기수정렬 구현
파이썬 기수정렬 구현

def radix_sort(a, base=10):
    size = len(a)
    maxval = max(a)
    exp = 1
    while exp <= maxval:
        output = [0]*size
        count = [0]*base
        for i in range(size): count[(a[i]//exp)%base] += 1
        for i in range(1,base): count[i]+=count[i-1]
        for i in range(size-1,-1,-1):
        	j = (a[i]//exp)%base
        	output[count[j]-1] = a[i]
        	count[j] -= 1
        for i in range(size): a[i]=output[i]
        exp *= base
arr = [9,1,22,4,0,1,22,100,10]
radix_sort( arr )
print( arr )
# [0, 1, 1, 4, 9, 10, 22, 22, 100]

def radix_sort(a, base=10):
    from math import log
    size = len(a)
    for i in range(int(log(max(a),base))+1):
        exp = base ** i
        output = [0]*size
        count = [0]*base
        for i in range(size): count[(a[i]//exp)%base] += 1
        for i in range(1,base): count[i]+=count[i-1]
        for i in range(size-1,-1,-1):
        	j = (a[i]//exp)%base
        	output[count[j]-1] = a[i]
        	count[j] -= 1
        for i in range(size): a[i]=output[i]
arr = [9,1,22,4,0,1,22,100,10]
radix_sort( arr )
print( arr )
# [0, 1, 1, 4, 9, 10, 22, 22, 100]

def radix_sort(a, base=10):
    def counting_sort(a, exp, base):
    	size = len(a)
    	output = [0]*size
    	count = [0]*base
    	for i in range(size):
    		index = int(a[i]/exp)
    		count[index%base] += 1
    	for i in range(1,base): count[i]+=count[i-1]
    	for i in range(size-1,-1,-1):
    		index = int(a[i]/exp)
    		output[count[index%base]-1] = a[i]
    		count[index%base] -= 1
    	for i in range(size): a[i]=output[i]
    maxval = max(a)
    exp = 1
    while exp <= maxval:
        counting_sort(a, exp, base)
        exp *= base
arr = [9,1,22,4,0,1,22,100,10]
radix_sort( arr )
print( arr )
# [0, 1, 1, 4, 9, 10, 22, 22, 100]

def radix_sort(a, base=10):
    def list_to_buckets(a, base, iteration):
        buckets = [[] for x in range(base)]
        for x in a:
            digit = (x // (base ** iteration)) % base
            buckets[digit].append(x)
        return buckets
    def buckets_to_list(buckets):
        a = []
        for bucket in buckets:
            for x in bucket:
                a.append(x)
        return a
    maxval = max(a)
    it = 0
    while base ** it <= maxval:
        a = buckets_to_list(list_to_buckets(a, base, it))
        it += 1
    return a
arr = [9,1,22,4,0,1,22,100,10]
arr = radix_sort(arr)
print( arr )
# [0, 1, 1, 4, 9, 10, 22, 22, 100]

2 같이 보기[ | ]