82 lines
1.6 KiB
C
82 lines
1.6 KiB
C
#include <stdlib.h>
|
|
#include <stdio.h>
|
|
#define array int*
|
|
|
|
int findMax(array A, int size) {
|
|
int i, max = A[0];
|
|
|
|
for(i = 1; i < size; i++)
|
|
if (A[i] > max)
|
|
max = A[i];
|
|
return max;
|
|
}
|
|
|
|
array cumulativeFreq (array A, int size, int exp) {
|
|
int i, radix;
|
|
array frequency = calloc(19, sizeof(int));
|
|
|
|
for (i = 0; i < size; i++) {
|
|
radix = A[i] / exp % 10;
|
|
frequency[10 + radix]++;
|
|
}
|
|
for (i = 1; i < 18; i++)
|
|
frequency[i] += frequency[i - 1];
|
|
return frequency;
|
|
}
|
|
|
|
void countingSort (array *A, int size, int exp) {
|
|
int i, radix;
|
|
array count = cumulativeFreq(*A, size, exp);
|
|
array sorted = malloc(size * sizeof(int));
|
|
|
|
for (i = 0; i < size; i++) {
|
|
radix = (*A)[i] / exp % 10;
|
|
sorted[count[9 + radix]++] = (*A)[i];
|
|
}
|
|
free(*A);
|
|
free(count);
|
|
*A = sorted;
|
|
}
|
|
|
|
void radixSort(array *A, int size) {
|
|
int exp, max = findMax(*A, size);
|
|
|
|
for (exp = 1; max / exp > 0; exp *= 10)
|
|
countingSort(A, size, exp);
|
|
}
|
|
|
|
array readArray (int *size) {
|
|
int d, i = 0;
|
|
char c;
|
|
array A;
|
|
|
|
*size = 1;
|
|
A = malloc(sizeof(int));
|
|
do {
|
|
if (!scanf(" %d", &d))
|
|
continue;
|
|
if (i == *size - 1) {
|
|
*size *= 2;
|
|
A = realloc(A, *size * sizeof(int));
|
|
}
|
|
A[i++] = d;
|
|
} while ((c = getchar()) != EOF && c != '\n');
|
|
*size = i;
|
|
return A;
|
|
}
|
|
|
|
int main () {
|
|
array A;
|
|
int i, size;
|
|
|
|
printf("This program performs an insertion sort.\nType in a sequence of values separated by spaces and press ENTER: ");
|
|
A = readArray(&size);
|
|
radixSort(&A, size);
|
|
|
|
printf("New sequence:\n");
|
|
for (i = 0; i < size; i++)
|
|
printf("%d ", A[i]);
|
|
printf("\n");
|
|
return 0;
|
|
}
|