forked from starrohan999/Hacktoberfest-Accepted
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Counting sort
57 lines (51 loc) · 1.34 KB
/
Counting sort
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
#include <iostream>
using namespace std;
// counting sort sorting algorithm
void CountingSort(int input_array[],int s, int r)
{
int output_array[s];
int count_array[r];
// initialize all elements to 0 in count array
for(int i=0;i<r;i++)
count_array[i]=0;
// to take a count of all elements in the input array
for(int i=0;i<s;i++)
++count_array[input_array[i]];
// cummulative count of count array to get the
// positions of elements to be stored in the output array
for(int i=1;i<r;i++)
count_array[i]=count_array[i]+count_array[i-1];
// placing input array elements into output array in proper
// positions such that the result is a sorted array in ASC order
for(int i=0;i<s;i++)
output_array[--count_array[input_array[i]]] = input_array[i];
// copy output array elements to input array
for(int i=0;i<s;i++)
input_array[i]=output_array[i];
}
int main()
{
int size=0;
int range = 10;
cout<<"Enter Size of array: "<<endl;
cin>>size;
int myarray[size];
cout<<"Enter "<<size<<" integers in any order in range of 0-9: "<<endl;
for(int i=0;i<size;i++)
{
cin>>myarray[i];
}
cout<<"Before Sorting"<<endl;
for(int i=0;i<size;i++)
{
cout<<myarray[i]<<" ";
}
cout<<endl;
CountingSort(myarray,size,range); // counting sort called
cout<<"After Sorting"<<endl;
for(int i=0;i<size;i++)
{
cout<<myarray[i]<<" ";
}
return 0;
}