Counting sort

general
,
1

Can we skip the step of making each c[i]=c[i]+c[i-1] and directly print all the elements from the c[i] originally produced ??like i did it below and it works fine.I have doubt in the complexity of creating output array b.plzz help

#include

using namespace std;

int main()

{

int a[15],c[10],b[10],R,N;

cout<<“Range=”;cin>>R; //Assuming range form 0 to R

cout<<“\no of elements”;cin>>N;

int i=0;

while(i!=N)

{

cin>>a[i];

i++;

}

for(i=0;i<=R;i++){c[i]=0;} // complexity O(R)

for(i=0;i<N;i++) //complexity O(N)

{

c[a[i]]++;

}

int k=0;

for(i=0;i<=R;i++)
{

while(c[i]!=0)

{

b[k]=i;

c[i]–;

k++;

}

}

//to print the array;

for(i=0;i<N;i++)

{

cout<<b[i]<<" ";

}

return 0;

}

2

Well the step c[i] = c[i] + c[i-1] is done to get number of elements less than equal to i in original array A … and here a while loop in your for loop made this solution non linear and non stable which was originally the essence of counting sort.

You can do whatever changes you like but with those changes if the complexity deteriorates then there is not any benefit. This program here is not a counting sort.

1 Like
3

@cOd3_k1ra yes u r right in my case sort will be non stable,i did n’t notice that.