최신판 |
당신의 편집 |
1번째 줄: |
1번째 줄: |
| [[분류: 기수정렬]] | | [[분류: 정렬]] |
| ==개요==
| |
| ;기수정렬 구현
| |
| * 기수(base)를 지정하여 정렬할 수 있음
| |
| :생략하면 기본값으로 10이 적용됨
| |
| * 일단 음수는 정렬 불가
| |
| | |
| ==C==
| |
| [[분류: C]]
| |
| {{참고|C언어 기수정렬 구현}}
| |
| <syntaxhighlight lang='c'>
| |
| #include <stdio.h>
| |
| #include <string.h>
| |
| void radix_sort(int a[], int size, int base) {
| |
| int ex, i, j, max = a[0];
| |
| for(i=1; i<size; i++) if(a[i]>max) max=a[i];
| |
| for(ex=1; ex<=max; ex*=base) {
| |
| int output[size], count[base];
| |
| memset(count,0,sizeof(count));
| |
| for(i=0; i<size; i++) count[(a[i]/ex)%base]++;
| |
| for(i=1; i<base; i++) count[i] += count[i-1];
| |
| for(i=size-1; i>-1; i--) {
| |
| j = (a[i]/ex)%base;
| |
| output[count[j]-1] = a[i];
| |
| count[j]--;
| |
| }
| |
| for(i=0; i<size; i++) a[i] = output[i];
| |
| }
| |
| }
| |
| int main() {
| |
| int arr[] = {9,1,22,4,0,1,22,100,10};
| |
| int size = sizeof(arr)/sizeof(int);
| |
| radix_sort(arr, size, 10);
| |
| for(int i=0; i<size; i++) printf("%d ", arr[i]);
| |
| // 0 1 1 4 9 10 22 22 100
| |
| }
| |
| </syntaxhighlight>
| |
| | |
| ==C++== | | ==C++== |
| [[분류: C++]] | | [[분류: C++]] |
| {{참고|C++ 기수정렬 구현}} | | {{참고|C++ 기수정렬 구현}} |
| <syntaxhighlight lang='cpp'> | | <source lang='cpp'> |
| #include <iostream>
| | </source> |
| void radix_sort(int a[], int size, int base) {
| |
| int ex, i, j, max = a[0];
| |
| for(i=1; i<size; i++) if(a[i]>max) max=a[i];
| |
| for(ex=1; ex<=max; ex*=base) {
| |
| int output[size], count[base] = {0};
| |
| for(i=0; i<size; i++) count[(a[i]/ex)%base]++;
| |
| for(i=1; i<base; i++) count[i] += count[i-1];
| |
| for(i=size-1; i>-1; i--) {
| |
| j = (a[i]/ex)%base;
| |
| output[count[j]-1] = a[i];
| |
| count[j]--;
| |
| }
| |
| for(i=0; i<size; i++) a[i] = output[i];
| |
| }
| |
| }
| |
| void radix_sort(int a[], int size) {
| |
| radix_sort(a, size, 10);
| |
| }
| |
| int main() {
| |
| int arr[] = {9,1,22,4,0,1,22,100,10};
| |
| radix_sort(arr, sizeof(arr)/sizeof(int));
| |
| for(int x: arr) std::cout << x << " ";
| |
| // 0 1 1 4 9 10 22 22 100
| |
| }
| |
| </syntaxhighlight>
| |
| | |
| ==C#==
| |
| [[분류: csharp]]
| |
| {{참고|C샵 기수정렬 구현}}
| |
| <syntaxhighlight lang='csharp'>
| |
| using System;
| |
| using System.Linq;
| |
| class Program {
| |
| static void radixSort(int[] a) {
| |
| radixSort(a, 10);
| |
| }
| |
| static void radixSort(int[] a, int bs) {
| |
| int max = a.Max();
| |
| int exp, i, j, size=a.Length;
| |
| for(exp=1; exp<=max; exp*=bs) {
| |
| int[] count = new int[bs];
| |
| int[] output = new int[size];
| |
| for(i=0; i<size; i++) count[(a[i]/exp)%bs]++;
| |
| for(i=1; i<bs; i++) count[i]+=count[i-1];
| |
| for(i=size-1; i>-1; i--) {
| |
| j = (a[i]/exp)%bs;
| |
| output[count[j]-1] = a[i];
| |
| count[j]--;
| |
| }
| |
| for(i=0; i<size; i++) a[i]=output[i];
| |
| }
| |
| }
| |
| static void Main() {
| |
| int[] arr = {9,1,22,4,0,1,22,100,10};
| |
| radixSort(arr);
| |
| Console.Write(string.Join(",",arr));
| |
| // 0,1,1,4,9,10,22,22,100
| |
| }
| |
| }
| |
| </syntaxhighlight> | |
|
| |
|
| ==Java== | | ==Java== |
| [[분류: Java]] | | [[분류: Java]] |
| {{참고|Java 기수정렬 구현}} | | {{참고|Java 기수정렬 구현}} |
| <syntaxhighlight lang='Java'> | | <source lang='Java'> |
| import java.util.Collections;
| | </source> |
| import java.util.Arrays;
| |
| public class MyClass {
| |
| static void radix_sort(Integer a[]) {
| |
| radix_sort(a, 10);
| |
| }
| |
| static void radix_sort(Integer a[], int base) {
| |
| int max = Collections.max(Arrays.asList(a));
| |
| int exp, i, j, size = a.length;
| |
| for(exp=1; exp<=max; exp*=base) {
| |
| int count[] = new int[base];
| |
| int output[] = new int[size];
| |
| for(i=0; i<size; i++) count[(a[i]/exp)%base]++;
| |
| for(i=1; i<base; i++) count[i]+=count[i-1];
| |
| for(i=size-1; i>-1; i--) {
| |
| j = (a[i]/exp)%base;
| |
| output[count[j]-1] = a[i];
| |
| count[j]--;
| |
| }
| |
| for(i=0; i<size; i++) a[i]=output[i];
| |
| }
| |
| }
| |
| public static void main(String args[]) {
| |
| Integer arr[] = {9,1,22,4,0,1,22,100,10};
| |
| radix_sort(arr);
| |
| for(int x: arr) System.out.format("%d ",x);
| |
| // 0 1 1 4 9 10 22 22 100
| |
| }
| |
| }
| |
| </syntaxhighlight>
| |
| | |
| ==PHP==
| |
| [[분류: PHP]]
| |
| {{참고|PHP 기수정렬 구현}}
| |
| <syntaxhighlight lang='php'>
| |
| <?php
| |
| function radix_sort(&$a, $base=10) {
| |
| $max = max($a);
| |
| $size = count($a);
| |
| for($exp=1; $exp<=$max; $exp*=$base) {
| |
| $count = array_fill(0,$base,0);
| |
| $output = array_fill(0,$size,0);
| |
| for($i=0; $i<$size; $i++) $count[intdiv($a[$i],$exp)%$base]++;
| |
| for($i=1; $i<$base; $i++) $count[$i]+=$count[$i-1];
| |
| for($i=$size-1; $i>-1; $i--) {
| |
| $j = intdiv($a[$i],$exp) % $base;
| |
| $output[$count[$j]-1] = $a[$i];
| |
| $count[$j]--;
| |
| }
| |
| for($i=0; $i<$size; $i++) $a[$i]=$output[$i];
| |
| }
| |
| }
| |
| $arr = [9,1,22,4,0,1,22,100,10];
| |
| radix_sort( $arr );
| |
| echo implode(',',$arr);
| |
| # 0,1,1,4,9,10,22,22,100
| |
| </syntaxhighlight> | |
|
| |
|
| ==Python== | | ==Python== |
| [[분류: Python]] | | [[분류: Python]] |
| {{참고|Python 기수정렬 구현}} | | {{참고|Python기수정렬 구현}} |
| <syntaxhighlight 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]
| | </source> |
| </syntaxhighlight> | |
| | |
| ==Ruby==
| |
| [[분류:ruby]]
| |
| {{참고|Ruby 기수정렬 구현}}
| |
| <syntaxhighlight lang='ruby'>
| |
| def radix_sort(a, base=10)
| |
| size = a.size
| |
| maxval = a.max()
| |
| ex = 1
| |
| while ex <= maxval
| |
| output = Array.new(size,0)
| |
| count = Array.new(base,0)
| |
| for i in (0...size); count[(a[i]/ex)%base]+=1; end
| |
| for i in (1...base); count[i]+=count[i-1]; end
| |
| for i in (size-1).downto(0)
| |
| j = (a[i]/ex)%base
| |
| output[count[j]-1] = a[i]
| |
| count[j] -= 1
| |
| end
| |
| for i in (0...size); a[i]=output[i]; end
| |
| ex *= base
| |
| end
| |
| end
| |
| arr = [9,1,22,4,0,1,22,100,10]
| |
| radix_sort(arr)
| |
| print arr
| |
| # [0, 1, 1, 4, 9, 10, 22, 22, 100]
| |
| </syntaxhighlight>
| |
|
| |
|
| ==같이 보기== | | ==같이 보기== |
| | * [[카운팅정렬 구현]] |
| | * [[정렬 구현]] |
| * [[기수정렬]] | | * [[기수정렬]] |
| * [[정렬 구현]]
| |
| * [[카운팅정렬 구현]]
| |
|
| |
|
| ==참고== | | ==참고== |
| * https://www.geeksforgeeks.org/radix-sort/ | | * https://www.geeksforgeeks.org/radix-sort/ |