기수정렬 구현

1 C++

C++ 기수정렬 구현 문서를 참고하십시오.

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

2 Java

Java 기수정렬 구현 문서를 참고하십시오.

import java.util.Arrays;
public class MyClass {
	static void count_sort(int arr[], int exp) {
		int size = arr.length;
		int output[] = new int[size];
		int count[] = new int[10];
		int i, index;
		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];
	}
	static void radix_sort(int arr[]) {
		int max = arr[0];
		for(int i:arr) if(max<i)max=i;
		for(int exp=1; max/exp>0; exp*=10) count_sort(arr, exp);
	}
	public static void main(String[] args) {
		int arr[] = {3,4,2,1,7,5,8,9,0,6,100,10};
		radix_sort(arr);
		System.out.println( Arrays.toString(arr) );
		// [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 100]
	}
}

3 PHP

PHP 기수정렬 구현 문서를 참고하십시오.

<?php
function radix_sort(&$a, $base=10) {
    $maxval = max($a);
    $size = count($a);
    for($exp=1; $exp<=$maxval; $exp*=$base) {
    	$count = array_fill(0,$base,0);
    	$output = array_fill(0,$size,0);
    	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=$size-1; $i>-1; $i--) {
    		$index = intdiv($a[$i],$exp);
    		$output[$count[$index%$base]-1] = $a[$i];
    		$count[$index%$base]--;
    	}
    	for($i=0; $i<$size; $i++) $a[$i]=$output[$i];
    }
}
$arr = [9,1,22,4,0,1,22,100,10];
radix_sort( $arr );
print( implode(' ',$arr) );
# 0 1 1 4 9 10 22 22 100

4 Python

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):
        	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]
arr = [9,1,22,4,0,1,22,100,10]
radix_sort( arr )
print( arr )
# [0, 1, 1, 4, 9, 10, 22, 22, 100]

5 같이 보기

• 기수정렬
• 정렬 구현
• 카운팅정렬 구현

6 참고

• https://www.geeksforgeeks.org/radix-sort/