편집을 취소할 수 있습니다. 이 편집을 되돌리려면 아래의 바뀐 내용을 확인한 후 게시해주세요.
최신판 | 당신의 편집 | ||
1번째 줄: | 1번째 줄: | ||
[[분류: 기수정렬]] | [[분류: 기수정렬]] | ||
==C++== | ==C++== | ||
[[분류: C++]] | [[분류: C++]] | ||
{{참고|C++ 기수정렬 구현}} | {{참고|C++ 기수정렬 구현}} | ||
< | <source lang='cpp'> | ||
#include <iostream> | #include<iostream> | ||
void | using namespace std; | ||
void count_sort(int arr[], int size, int exp) { | |||
int i, index, output[size], count[10] = {0}; | |||
for(i=0; i<size; i++) count[(arr[i]/exp)%10]++; | |||
for(i=1; i<10; i++) count[i] += count[i-1]; | |||
for(i=size-1; i>-1; i--) { | |||
index = arr[i]/exp; | |||
output[count[index%10]-1] = arr[i]; | |||
count[index%10]--; | |||
} | |||
for(i=0; i<size; i++) arr[i] = output[i]; | |||
} | } | ||
void radix_sort(int | void radix_sort(int arr[], int size) { | ||
int max = arr[0]; | |||
for(int i=1; i<size; i++) if(arr[i]>max) max=arr[i]; | |||
for(int exp=1; max/exp>0; exp*=10) count_sort(arr, size, exp); | |||
} | } | ||
int main() { | int main() { | ||
int arr[] = {3,4,2,1,7,5,8,9,0,6,100,10}; | |||
int size = sizeof(arr)/sizeof(arr[0]); | |||
radix_sort(arr, size); | |||
for(int i=0; i<size; i++) cout << arr[i] << " "; | |||
// 0 1 2 3 4 5 6 7 8 9 10 100 | |||
} | } | ||
</ | </source> | ||
==Java== | ==Java== | ||
[[분류: Java]] | [[분류: Java]] | ||
{{참고|Java 기수정렬 구현}} | {{참고|Java 기수정렬 구현}} | ||
< | <source lang='Java'> | ||
import java.util.Collections; | import java.util.Collections; | ||
import java.util.Arrays; | import java.util.Arrays; | ||
136번째 줄: | 64번째 줄: | ||
} | } | ||
} | } | ||
</ | </source> | ||
==PHP== | ==PHP== | ||
[[분류: PHP]] | [[분류: PHP]] | ||
{{참고|PHP 기수정렬 구현}} | {{참고|PHP 기수정렬 구현}} | ||
< | <source lang='php'> | ||
<?php | <?php | ||
function radix_sort(&$a, $base=10) { | function radix_sort(&$a, $base=10) { | ||
$ | $maxval = max($a); | ||
$size = count($a); | $size = count($a); | ||
for($exp=1; $exp<=$ | for($exp=1; $exp<=$maxval; $exp*=$base) { | ||
$count = array_fill(0,$base,0); | $count = array_fill(0,$base,0); | ||
$output = array_fill(0,$size,0); | $output = array_fill(0,$size,0); | ||
for($i=0; $i<$size; $i++) $ | for($i=0; $i<$size; $i++) { | ||
$index = intdiv($a[$i],$exp); | |||
$count[$index%$base]++; | |||
} | |||
for($i=1; $i<$base; $i++) $count[$i]+=$count[$i-1]; | for($i=1; $i<$base; $i++) $count[$i]+=$count[$i-1]; | ||
for($i=$size-1; $i>-1; $i--) { | for($i=$size-1; $i>-1; $i--) { | ||
$ | $index = intdiv($a[$i],$exp); | ||
$output[$count[$ | $output[$count[$index%$base]-1] = $a[$i]; | ||
$count[$ | $count[$index%$base]--; | ||
} | } | ||
for($i=0; $i<$size; $i++) $a[$i]=$output[$i]; | for($i=0; $i<$size; $i++) $a[$i]=$output[$i]; | ||
161번째 줄: | 92번째 줄: | ||
$arr = [9,1,22,4,0,1,22,100,10]; | $arr = [9,1,22,4,0,1,22,100,10]; | ||
radix_sort( $arr ); | radix_sort( $arr ); | ||
print( implode(' ',$arr) ); | |||
# 0 | # 0 1 1 4 9 10 22 22 100 | ||
</ | </source> | ||
==Python== | ==Python== | ||
[[분류: Python]] | [[분류: Python]] | ||
{{참고|Python 기수정렬 구현}} | {{참고|Python 기수정렬 구현}} | ||
< | <source lang='Python'> | ||
def radix_sort(a, base=10): | def radix_sort(a, base=10): | ||
from math import log | |||
size = len(a) | size = len(a) | ||
for i in range(int(log(max(a),base))+1): | |||
exp = base ** i | |||
output = [0]*size | output = [0]*size | ||
count = [0]*base | count = [0]*base | ||
for i in range(size): | 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(1,base): count[i]+=count[i-1] | ||
for i in range(size-1,-1,-1): | for i in range(size-1,-1,-1): | ||
index = int(a[i]/exp) | |||
output[count[ | output[count[index%base]-1] = a[i] | ||
count[ | count[index%base] -= 1 | ||
for i in range(size): a[i]=output[i] | for i in range(size): a[i]=output[i] | ||
arr = [9,1,22,4,0,1,22,100,10] | arr = [9,1,22,4,0,1,22,100,10] | ||
radix_sort( arr ) | radix_sort( arr ) | ||
print( arr ) | print( arr ) | ||
# [0, 1, 1, 4, 9, 10, 22, 22, 100] | # [0, 1, 1, 4, 9, 10, 22, 22, 100] | ||
</ | </source> | ||
==같이 보기== | ==같이 보기== |