-
Notifications
You must be signed in to change notification settings - Fork 1
/
Count_sort.c
59 lines (59 loc) · 1.1 KB
/
Count_sort.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <stdio.h>
#include <stdlib.h>
int maximum(int A[], int n)
{
int max = A[0];
for (int i = 1; i < n; i++)
{
if (A[i] > max)
{
max = A[i];
}
}
return max;
}
void count_sort(int A[], int n)
{
int maxim = maximum(A, n);
int *count;
count = (int *)malloc((maxim + 1) * sizeof(int));
int i;
for (i = 0; i < (maxim + 1); i++)
{
count[i] = 0;
}
for (i = 0; i < n; i++)
{
count[A[i]]++;
}
i = 0;
static int k = 0;
while (k < n)
{
if (count[i] == 0)
{
i++;
}
else
{
while (count[i] != 0)
{
A[k] = i;
count[i]--;
k++;
}
i++;
}
}
}
int main()
{
int A[] = {2, 3, 4, 5, 2, 3, 6, 8};
count_sort(A, 8);
for (int i = 0; i < 8; i++)
{
printf("%d ", A[i]);
}
}
/*Count sort takes a large amount of space due to creation of an array of
maximum size possible.*/