C/C++ による計数ソートの実装
計数ソート
#include <stdio.h>
void countSort(int array[], int array_size) {
int sorted_array[array_size];
// calculate how many elements should be prepared
int max = array[0];
for(int i = 1; i < array_size; i++) {
if(array[i] > max) {
max = array[i];
}
}
// prepare array for counting
int count[max + 1];
for (int i = 0; i < max + 1; i++) {
count[i] = 0;
}
// couting
for(int i = 0; i < array_size; i++) {
count[array[i]]++;
}
// make a hash to output sorted index
for (int i = 1; i < max + 1; i++) {
count[i] += count[i - 1];
}
// sorting
for (int i = 0; i < array_size; i++) {
sorted_array[count[array[i]] - 1] = array[i];
count[array[i]]--;
}
// copy sorted elements to the original array
for (int i = 0; i < array_size; i++) {
array[i] = sorted_array[i];
}
}
int main (void) {
int i;
int array[10] = {3, 6, 1, 7, 2, 0, 4, 5, 9, 8};
printf(" array: ");
for (i = 0; i < sizeof(array) / sizeof(array[0]); i++) {
printf("%d ", array[i]);
}
printf("\n");
quickSort(array, 0, sizeof(array) / sizeof(array[0]) - 1);
printf("sorted array: ");
for (i = 0; i < sizeof(array) / sizeof(array[0]); i++) {
printf("%d ", array[i]);
}
printf("\n");
return 0;
}