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

4번째 줄: 4번째 줄:
{{참고|C++ 기수정렬 구현}}
{{참고|C++ 기수정렬 구현}}
<source lang='cpp'>
<source lang='cpp'>
#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
}
</source>
</source>



2018년 7월 16일 (월) 01:10 판

1 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

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 Python

def count_sort(arr, exp):
	size = len(arr)
	output = [0]*size
	count = [0]*10
	for i in range(size):
		index = int(arr[i]/exp)
		count[index%10] += 1
	for i in range(1,10):
		count[i] += count[i-1]
	for i in range(size-1,-1,-1):
		index = int(arr[i]/exp)
		output[count[index%10]-1] = arr[i]
		count[index%10] -= 1
	for i in range(size):
		arr[i] = output[i]
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 )
print( arr )
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 100]

4 같이 보기

5 참고

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