개요
- 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]
같이 보기
