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

잔글 (봇: 자동으로 텍스트 교체 (-source +syntaxhighlight))
 
(다른 사용자 한 명의 중간 판 25개는 보이지 않습니다)
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'>
#include<iostream>
#include <iostream>
using namespace std;
void radix_sort(int a[], int size, int base) {
void count_sort(int arr[], int size, int exp) {
    int ex, i, j, max = a[0];
int i, index, output[size], count[10] = {0};
    for(i=1; i<size; i++) if(a[i]>max) max=a[i];
for(i=0; i<size; i++) count[(arr[i]/exp)%10]++;
    for(ex=1; ex<=max; ex*=base) {
for(i=1; i<10; i++) count[i] += count[i-1];
    int output[size], count[base] = {0};
for(i=size-1; i>-1; i--) {
    for(i=0; i<size; i++) count[(a[i]/ex)%base]++;
index = arr[i]/exp;
    for(i=1; i<base; i++) count[i] += count[i-1];
output[count[index%10]-1] = arr[i];
    for(i=size-1; i>-1; i--) {
count[index%10]--;
    j = (a[i]/ex)%base;
}
    output[count[j]-1] = a[i];
for(i=0; i<size; i++) arr[i] = output[i];
    count[j]--;
    }
    for(i=0; i<size; i++) a[i] = output[i];
    }
}
}
void radix_sort(int arr[], int size) {
void radix_sort(int a[], int size) {
int max = arr[0];
    radix_sort(a, size, 10);
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 arr[] = {9,1,22,4,0,1,22,100,10};
int size = sizeof(arr)/sizeof(arr[0]);
    radix_sort(arr, sizeof(arr)/sizeof(int));
radix_sort(arr, size);
    for(int x: arr) std::cout << x << " ";
for(int i=0; i<size; i++) cout << arr[i] << " ";
    // 0 1 1 4 9 10 22 22 100
// 0 1 2 3 4 5 6 7 8 9 10 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
    }
}
}
</source>
</syntaxhighlight>


==Java==
==Java==
[[분류: Java]]
[[분류: Java]]
{{참고|Java 기수정렬 구현}}
{{참고|Java 기수정렬 구현}}
<source lang='Java'>
<syntaxhighlight lang='Java'>
import java.util.Collections;
import java.util.Arrays;
import java.util.Arrays;
public class MyClass {
public class MyClass {
static void count_sort(int arr[], int exp) {
    static void radix_sort(Integer a[]) {
int size = arr.length;
        radix_sort(a, 10);
int output[] = new int[size];
    }
int count[] = new int[10];
    static void radix_sort(Integer a[], int base) {
int i, index;
        int max = Collections.max(Arrays.asList(a));
for(i=0; i<size; i++) count[ (arr[i]/exp)%10 ]++;
        int exp, i, j, size = a.length;
for(i=1; i<10; i++) count[i] += count[i-1];
        for(exp=1; exp<=max; exp*=base) {
for(i=size-1; i>-1; i--) {
            int count[] = new int[base];
index = arr[i]/exp;
            int output[] = new int[size];
output[count[index%10]-1] = arr[i];
            for(i=0; i<size; i++) count[(a[i]/exp)%base]++;
count[index%10]--;
            for(i=1; i<base; i++) count[i]+=count[i-1];
}
            for(i=size-1; i>-1; i--) {
for(i=0; i<size; i++) arr[i] = output[i];
                j = (a[i]/exp)%base;
}
                output[count[j]-1] = a[i];
static void radix_sort(int arr[]) {
                count[j]--;
int max = arr[0];
            }
for(int i:arr) if(max<i)max=i;
            for(i=0; i<size; i++) a[i]=output[i];
for(int exp=1; max/exp>0; exp*=10) count_sort(arr, exp);
        }
}
    }
public static void main(String[] args) {
    public static void main(String args[]) {
int arr[] = {3,4,2,1,7,5,8,9,0,6,100,10};
Integer arr[] = {9,1,22,4,0,1,22,100,10};
radix_sort(arr);
radix_sort(arr);
System.out.println( Arrays.toString(arr) );
for(int x: arr) System.out.format("%d ",x);
// [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 100]
// 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];
    }
}
}
</source>
$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'>
def count_sort(arr, exp):
def radix_sort(a, base=10):
size = len(arr)
    size = len(a)
output = [0]*size
    maxval = max(a)
count = [0]*10
    exp = 1
for i in range(size):
    while exp <= maxval:
index = int(arr[i]/exp)
        output = [0]*size
count[index%10] += 1
        count = [0]*base
for i in range(1,10):
        for i in range(size): count[(a[i]//exp)%base] += 1
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(arr[i]/exp)
        j = (a[i]//exp)%base
output[count[index%10]-1] = arr[i]
        output[count[j]-1] = a[i]
count[index%10] -= 1
        count[j] -= 1
for i in range(size):
        for i in range(size): a[i]=output[i]
arr[i] = output[i]
        exp *= base
def radix_sort(arr):
arr = [9,1,22,4,0,1,22,100,10]
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, 2, 3, 4, 5, 6, 7, 8, 9, 10, 100]
# [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/

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