70 lines
1.5 KiB
C
70 lines
1.5 KiB
C
#include <stdlib.h>
|
|
#include <stdio.h>
|
|
#include <limits.h>
|
|
#define array int*
|
|
|
|
array readArray (int *size, int *max) {
|
|
int d, i = 0;
|
|
char c;
|
|
array A;
|
|
|
|
*max = 0;
|
|
*size = 1;
|
|
A = malloc(sizeof(int));
|
|
do {
|
|
if (!scanf(" %d", &d))
|
|
continue;
|
|
if (i == *size - 1) {
|
|
*size *= 2;
|
|
A = realloc(A, *size * sizeof(int));
|
|
}
|
|
if (d > *max)
|
|
*max = d;
|
|
A[i++] = d;
|
|
} while ((c = getchar()) != EOF && c != '\n');
|
|
*size = i;
|
|
return A;
|
|
}
|
|
|
|
array cumulativeFrequency(array A, int size, int max) {
|
|
int i;
|
|
array frequency = calloc((max + 1), sizeof(int));
|
|
|
|
for (i = 0; i < size; i++)
|
|
frequency[A[i] + 1]++;
|
|
for (i = 1; i <= max; i++)
|
|
frequency[i] += frequency[i - 1];
|
|
return frequency;
|
|
}
|
|
|
|
void countingSort (array* A, int size, int max) {
|
|
int i;
|
|
array count = cumulativeFrequency(*A, size, max);
|
|
array sorted = malloc(size * sizeof(int));
|
|
|
|
for (i = 0; i < size; i++) {
|
|
sorted[count[(*A)[i]]] = (*A)[i];
|
|
count[(*A)[i]]++;
|
|
}
|
|
free(*A);
|
|
free(count);
|
|
*A = sorted;
|
|
}
|
|
|
|
int main () {
|
|
int i, size, max;
|
|
array A;
|
|
|
|
printf("Este programa admite uma lista de valores inteiros x tais que %d ≤ x ≤ %d e os ordena em ordem crescente.\nDigite uma série de valores inteiros separadas entre si por espaço e pressione ENTER:\n", 0, INT_MAX);
|
|
A = readArray(&size, &max);
|
|
|
|
countingSort(&A, size, max);
|
|
|
|
printf("Arranjo ordenado:\n");
|
|
for (i = 0; i < size; i++)
|
|
printf("%d ", A[i]);
|
|
printf("\n");
|
|
free(A);
|
|
return 0;
|
|
}
|