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

(새 문서: 분류: 정렬 ==C++== 분류: C++ {{참고|C++ 기수정렬 구현}} <source lang='cpp'> </source> ==Java== 분류: Java {{참고|Java 기수정렬 구현}} <source lang...)
 
잔글 (봇: 자동으로 텍스트 교체 (-source +syntaxhighlight))
 
(다른 사용자 한 명의 중간 판 30개는 보이지 않습니다)
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++ 기수정렬 구현}}
<source lang='cpp'>
<syntaxhighlight lang='cpp'>
</source>
#include <iostream>
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 기수정렬 구현}}
<source lang='Java'>
<syntaxhighlight lang='Java'>
</source>
import java.util.Collections;
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 기수정렬 구현}}
<source lang='Java'>
<syntaxhighlight lang='Python'>
</source>
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]
</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/

2020년 11월 2일 (월) 02:31 기준 최신판

1 개요[ | ]

기수정렬 구현
  • 기수(base)를 지정하여 정렬할 수 있음
생략하면 기본값으로 10이 적용됨
  • 일단 음수는 정렬 불가

2 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 
}

3 C++[ | ]

#include <iostream>
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 
}

4 C#[ | ]

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
    }
}

5 Java[ | ]

import java.util.Collections;
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 
    }
}

6 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

7 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]

8 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]

9 같이 보기[ | ]

10 참고[ | ]

문서 댓글 ({{ doc_comments.length }})
{{ comment.name }} {{ comment.created | snstime }}