tag:blogger.com,1999:blog-8285804830535272268.post888623995431464502..comments2023-07-02T00:41:27.422-07:00Comments on C Programming Tutorial: Counting Sort Program In CMantu Kumarhttp://www.blogger.com/profile/02897308282659594376noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-8285804830535272268.post-70557053162234028542016-02-05T12:23:49.127-08:002016-02-05T12:23:49.127-08:00Check this:
#include
void counting_sort(int a[],i...Check this:<br /><br />#include<br />void counting_sort(int a[],int n,int max)<br />{<br /> int count[50]={0},i,j;<br /> for(i=0;imax)<br /> {<br /> max=a[i];<br /> }<br /> }<br /> counting_sort(a,n,max);<br /> return 0;<br />}<br /> /*4 14 8 0 2 5 2 1 0 22*/<br />Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8285804830535272268.post-11725525020598239072015-04-12T09:55:38.936-07:002015-04-12T09:55:38.936-07:00Let n=8
a[1 . . . 8] : 2 5 3 0 2 3 0 3
Elements a...Let n=8<br /><br />a[1 . . . 8] : 2 5 3 0 2 3 0 3<br />Elements are stored from index position 1.<br /><br />// Initializing auxiliary array<br /> for(i=0;i<=max_element;i++)<br /> {<br /> aux_array[i]=0;<br /> }<br /><br />aux_array[0...5]=0 0 0 0 0 0<br /><br />// Placing Frequency of each element in aux_array<br /> for(j=1;j<=n;j++)<br /> {<br /> aux_array[a[j]]=aux_array[a[j]]+1;<br /> }<br /><br />Now aux_array[0. . . 5] : 2 0 2 3 0 1<br />Elements are stored from index position 0.<br /><br />/* Adding elements of current and previous index position of aux_array<br /> for(i=1;i<=max_element;i++)<br /> {<br /> aux_array[i]=aux_array[i]+aux_array[i-1];<br /> }<br />Note : We are placing elements from index position 1 <br />So, aux_array[0]=2<br /><br />aux_array[1]=aux_array[1]+aux_array[0]<br />aux_array[1] = 0 + 2 = 2<br />Now aux_array[1]=2 // i.e we have 2 at index position 1 of aux_array<br /><br />Similarly on next loops : <br /><br />aux_array[2] = aux_array[2]+aux_array[1]<br />aux_array[2] = 2+2 = 4<br />aux_array[2] = 4<br /><br /><br />aux_array[3] = aux_array[3]+aux_array[2]<br />aux_array[3] = 3+4 = 7<br />aux_array[3] = 7<br /><br />and so on..<br /><br />After loop is finished then we will have : <br />aux_array[0...5] = 2 2 4 7 7 8<br /><br /> // Placing elements in sorted_array <br /> for(j=n;j>=1;j--)<br /> {<br /> sorted_array[aux_array[a[j]]] = a[j];<br /> aux_array[a[j]] = aux_array[a[j]] - 1;<br /> }<br /><br />Here we are placing elements in ascending order in sorted_array<br /><br />We have :<br />n=8<br /><br />For j=8<br />a[1...8]=2 5 3 0 2 3 0 3<br />aux_array[0...5] = 2 2 4 7 7 8<br /><br />sorted_array[aux_array[a[j]]] = a[j];<br />sorted_array[aux_array[a[8]]] <br />i.e sorted_array[aux_array[3]]<br />i.e sorted_array[7]=3<br /><br />aux_array[a[j]] = aux_array[a[j]] - 1;<br />aux_array[a[8]] = aux_array[a[8]]-1;<br />aux_array[3] = aux_array[3]-1;<br />aux_array[3] = 7-1 = 6<br /><br />For j=7<br />a[1...8]=2 5 3 0 2 3 0 3<br />aux_array[0...5] = 2 2 4 6 7 8<br /><br />sorted_array[aux_array[a[j]]] = a[j];<br />sorted_array[aux_array[a[7]]] <br />i.e sorted_array[aux_array[0]]<br />i.e sorted_array[2]=0<br /><br />aux_array[a[j]] = aux_array[a[j]] - 1;<br />aux_array[a[7]] = aux_array[a[7]]-1;<br />aux_array[0] = aux_array[0]-1;<br />aux_array[0] = 2-1 = 1<br /><br />For j=6<br />a[1...8]=2 5 3 0 2 3 0 3<br />aux_array[0...5] = 1 2 4 6 7 8<br /><br /><br />sorted_array[aux_array[a[j]]] = a[j];<br />sorted_array[aux_array[a[6]]] <br />i.e sorted_array[aux_array[3]]<br />i.e sorted_array[6]=3<br /><br />aux_array[a[j]] = aux_array[a[j]] - 1;<br />aux_array[a[6]] = aux_array[a[6]]-1;<br />aux_array[3] = aux_array[3]-1;<br />aux_array[3] = 6-1 = 5<br /><br />For j=5<br />a[1...8]=2 5 3 0 2 3 0 3<br />aux_array[0...5] = 1 2 4 5 7 8<br /><br /><br />sorted_array[aux_array[a[j]]] = a[j];<br />sorted_array[aux_array[a[5]]] <br />i.e sorted_array[aux_array[2]]<br />i.e sorted_array[4]=2<br /><br />aux_array[a[j]] = aux_array[a[j]] - 1;<br />aux_array[a[5]] = aux_array[a[5]]-1;<br />aux_array[2] = aux_array[2]-1;<br />aux_array[2] = 4-1 = 3<br /><br />We have aux_array[0...5] = 1 2 3 5 7 8<br /><br />Till now we have found : <br /><br />sorted_array[2]=0<br />sorted_array[4]=2<br />sorted_array[6]=3<br />sorted_array[7]=3<br /><br />Similarly follow the above step till j=1 and you will get elements in ascending order in sorted_array : <br /><br />sorted_array[1]=0<br />sorted_array[2]=0<br />sorted_array[3]=2<br />sorted_array[4]=2<br />sorted_array[5]=3<br />sorted_array[6]=3<br />sorted_array[7]=3<br />sorted_array[8]=5<br /><br />Hope this explanation is helpful to you..<br />Mantu Kumarhttps://www.blogger.com/profile/02897308282659594376noreply@blogger.comtag:blogger.com,1999:blog-8285804830535272268.post-7018714066803418112015-04-11T11:14:08.664-07:002015-04-11T11:14:08.664-07:00// Adding elements of current and previous index p... // Adding elements of current and previous index position<br /> for(i=1;i<=max_element;i++)<br /> {<br /> aux_array[i]=aux_array[i]+aux_array[i-1];<br /> }<br /> <br /> // Placing elements in sorted_array <br /> for(j=n;j>=1;j--)<br /> {<br /> sorted_array[aux_array[a[j]]] = a[j];<br /> aux_array[a[j]] = aux_array[a[j]] - 1;<br /> }<br />i can't understand this please help me..<br />Apu Kumar Chakrobortihttps://www.blogger.com/profile/06220411991891847715noreply@blogger.com