#include <stdio.h>
#include <stdlib.h>
void countingSort(int arr[], size_t n);
int main() {
int arr[] = {4, 2, 2, 8, 3, 3, 1};
size_t n = sizeof(arr) / sizeof(arr[0]);
countingSort(arr, n);
printf("Sorted array: ");
for (size_t i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}
void countingSort(int arr[], size_t n) {
int max = 0;
for (size_t i = 0; i < n; i++) {
if (arr[i] > max)
max = arr[i];
}
int count = (int )malloc((max + 1) * sizeof(int));
if (count == NULL) {
printf("Memory allocation failed");
exit(EXIT_FAILURE);
}
for (size_t i = 0; i <= max; i++)
count[i] = 0;
for (size_t i = 0; i < n; i++)
count[arr[i]]++;
for (size_t i = 1; i <= max; i++)
count[i] += count[i - 1];
int output = (int )malloc(n * sizeof(int));
if (output == NULL) {
printf("Memory allocation failed");
exit(EXIT_FAILURE);
}
for (size_t i = n - 1; i > 0; i--) {
output[count[arr[i]] - 1] = arr[i];
count[arr[i]]--;
}
for (size_t i = 0; i < n; i++)
arr[i] = output[i];
free(count);
free(output);
}