C++ 기수정렬 구현

1 개요[ | ]

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 
}

#include <iostream>
void radix_counting_sort(int a[], int size, int ex, int base) {
	int i, j, 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, int base) {
	int i, max = a[0];
	for(i=1; i<size; i++) if(a[i]>max) max=a[i];	
	for(i=1; i<=max; i*=base) radix_counting_sort(a, size, i, base);
}
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 
}

2 같이 보기[ | ]