| 최신판 |
당신의 편집 |
| 3번째 줄: |
3번째 줄: |
| ;파이썬 기수정렬 구현 | | ;파이썬 기수정렬 구현 |
|
| |
|
| <source lang='python'> | | <source lang='Java'> |
| def radix_sort(a, base=10): | | def count_sort(arr, exp): |
| size = len(a)
| | size = len(arr) |
| maxval = max(a)
| | output = [0]*size |
| exp = 1
| | count = [0]*10 |
| while exp <= maxval:
| | for i in range(size): |
| output = [0]*size
| | index = int(arr[i]/exp) |
| count = [0]*base
| | count[index%10] += 1 |
| for i in range(size): count[(a[i]//exp)%base] += 1
| | for i in range(1,10): |
| for i in range(1,base): count[i]+=count[i-1]
| | count[i] += count[i-1] |
| for i in range(size-1,-1,-1):
| | for i in range(size-1,-1,-1): |
| j = (a[i]//exp)%base
| | index = int(arr[i]/exp) |
| output[count[j]-1] = a[i]
| | output[count[index%10]-1] = arr[i] |
| count[j] -= 1
| | count[index%10] -= 1 |
| for i in range(size): a[i]=output[i]
| | for i in range(size): |
| exp *= base
| | arr[i] = output[i] |
| arr = [9,1,22,4,0,1,22,100,10] | | def radix_sort(arr): |
| | mx = max(arr) |
| | exp = 1 |
| | while mx/exp > 0: |
| | count_sort(arr, exp) |
| | exp *= 10 |
| | arr = [3,4,2,1,7,5,8,9,0,6,100,10] |
| radix_sort( arr ) | | radix_sort( arr ) |
| print( arr ) | | print( arr ) |
| # [0, 1, 1, 4, 9, 10, 22, 22, 100] | | # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 100] |
| </source>
| |
| <source lang='python'>
| |
| 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]
| |
| </source>
| |
| <source lang='python'>
| |
| 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]
| |
| </source>
| |
| <source lang='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( arr )
| |
| # [0, 1, 1, 4, 9, 10, 22, 22, 100]
| |
| </source> | | </source> |
|
| |
|
| ==같이 보기== | | ==같이 보기== |
| | * [[Python 카운팅정렬 구현]] |
| | * [[기수정렬 구현]] |
| * [[기수정렬]] | | * [[기수정렬]] |
| * [[기수정렬 구현]]
| |
| * [[Python 카운팅정렬 구현]]
| |
|
| |
|
| [[분류: Python 정렬]] | | [[분류: Python 정렬]] |
| [[분류: 기수정렬]] | | [[분류: 기수정렬]] |
