CountingSort.c

#include <stdio.h>
#include <stdlib.h>

// CountingSort - Ordenação por Contagem - Matheus Martins Batista -
// Universidade Federal de Itajuba - 2021

// Necessário encontrar o maior elemento para alocar o vetor auxiliar de
// contagem
int findMax(int *arr, int tam) {
  int max = arr[0];

  for (int i = 1; i < tam; i++) {
    if (arr[i] > max) {
      max = arr[i];
    }
  }

  return max;
}

// Ordena os valores presentes em A e armazena em B
void countingSort(int *arrA, int *arrB, int tam) {
  // Vetor de contagem terá a frequência que um número aparece no vetor
  // deve-se setar 0 para todos os elementos ou usar calloc
  int max = findMax(arrA, tam);
  int *count = calloc(max + 1, sizeof(int));

  // Frequência que determinado valor aparece no vetor
  for (int i = 0; i < tam; i++) {
    count[arrA[i]]++;
  }

  // Acumulativo da frequência dos valores menores que um elemento i do vetor
  // original (A)
  for (int i = 1; i <= max; i++) {
    count[i] += count[i - 1];
  }

  // Percorrer o vetor original com início no último elemento, subtituindo os
  // indices nos elementos do vetor count e decrescendo a cada atribuição
  for (int i = tam - 1; i >= 0; i--) {
    arrB[count[arrA[i]] - 1] = arrA[i];
    count[arrA[i]]--;
  }
}

int main() {
  int *arrA, *arrB;
  int tam = 10;
  arrA = malloc(tam * sizeof(int));
  arrB = calloc(tam, sizeof(int));

  // Popular vetor A
  srand(48 + tam);
  for (int j = 0; j < tam; j++)
    arrA[j] = rand() % 100;

  countingSort(arrA, arrB, tam);

  printf("Vetor ordenado: ");
  for (int i = 0; i < tam; i++) {
    printf("%d ", arrB[i]);
  }

  return 0;
}