"Python 기수정렬 구현"의 두 판 사이의 차이

2018년 8월 27일 (월) 01:05 판

1 개요

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

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( " ".join(map(str,arr)) )
# 0 1 1 4 9 10 22 22 100

2 같이 보기

@@ 4번째 줄: / 4번째 줄: @@
 <source lang='Java'>
-def count_sort(arr, exp):
+def radix_sort(a, base=10):
-	size = len(arr)
+    def list_to_buckets(a, base, iteration):
-	output = [0]*size
+        buckets = [[] for x in range(base)]
-	count = [0]*10
+        for x in a:
-	for i in range(size):
+            digit = (x // (base ** iteration)) % base
-		index = int(arr[i]/exp)
+            buckets[digit].append(x)
-		count[index%10] += 1
+        return buckets
-	for i in range(1,10):
+    def buckets_to_list(buckets):
-		count[i] += count[i-1]
+        a = []
-	for i in range(size-1,-1,-1):
+        for bucket in buckets:
-		index = int(arr[i]/exp)
+            for x in bucket:
-		output[count[index%10]-1] = arr[i]
+                a.append(x)
-		count[index%10] -= 1
+        return a
-	for i in range(size):
+    maxval = max(a)
-		arr[i] = output[i]
+    it = 0
-def radix_sort(arr):
+    while base ** it <= maxval:
-	mx = max(arr)
+        a = buckets_to_list(list_to_buckets(a, base, it))
-	exp = 1
+        it += 1
-	while mx/exp > 0:
+    return a
-		count_sort(arr, exp)
+arr = [9,1,22,4,0,1,22,100,10]
-		exp *= 10
+arr = radix_sort(arr)
-arr = [3,4,2,1,7,5,8,9,0,6,100,10]
+print( " ".join(map(str,arr)) )
-radix_sort( arr )
+# 0 1 1 4 9 10 22 22 100
-print( arr )
-# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 100]
 </source>