main.c

1#include <stdio.h>
2#include <stdlib.h>
3
4void countingSort(int arr[], int n)
5{
6    int i;
7    int max = arr[0], min = arr[0];
8
9    for (i = 1; i < n; i++)
10    {
11        if (arr[i] > max)
12            max = arr[i];
13        if (arr[i] < min)
14            min = arr[i];
15    }
16
17    int range = max - min + 1;
18    int *count = (int *)calloc(range, sizeof(int));
19    int output[n];
20
21    for (i = 0; i < n; i++)
22        count[arr[i] - min]++;
23
24    for (i = 1; i < range; i++)
25        count[i] += count[i - 1];
26
27    for (i = n - 1; i >= 0; i--)
28    {
29        output[count[arr[i] - min] - 1] = arr[i];
30        count[arr[i] - min]--;
31    }
32
33    for (i = 0; i < n; i++)
34        arr[i] = output[i];
35
36    free(count);
37}
38
39void printArray(int arr[], int n)
40{
41    for (int i = 0; i < n; i++)
42        printf("%d ", arr[i]);
43    printf("\n");
44}
45
46int main()
47{
48    int arr[] = {4, -2, -2, 8, 3, -1, 1};
49    int n = sizeof(arr) / sizeof(arr[0]);
50
51    printf("Original array: ");
52    printArray(arr, n);
53
54    countingSort(arr, n);
55
56    printf("Sorted array:   ");
57    printArray(arr, n);
58
59    return 0;
60}