470,866 Members | 1,943 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 470,866 developers. It's quick & easy.

A question on Sorting by Comparision Counting

In TAOCP, Volume 3 - Sorting and Searching, Page Number -77, an
algorithm for Sorting by Comparision Counting is given. I understand
the algorithm. What I do not understand is Knuth has stated that the
running time of the program is 13N + 6A + 5B - 4;

This is the C++ snippet I am using

bool SortByComparisionCount()
{
// I use 87 instead of 087 and 61 instead of
061
int aKeys[] = {503, 87,
512, 61,
908, 170, 897, 275,
653, 426, 154, 509,
612, 677, 765, 703};

int aCountList[] = {0, 0, 0, 0,
0, 0, 0, 0,
0, 0, 0, 0,
0, 0, 0, 0,};

int aSortedList[] = {0, 0, 0, 0,
0, 0, 0, 0,
0, 0, 0, 0};

int aKeyCount = 16;

for(int i = aKeyCount - 1; i 0; i--)
{
for(int j = i-1; j >= 0; j--)
{
if(aKeys[i] <= aKeys[j])
{
++aCountList[j];
}
else
{
++aCountList[i];
}
}
}

for( int j = 0; j < aKeyCount; j++)
{
aSortedList[aCountList[j]] = aKeys[j];
}

return true;
}
For me as a C++ programmer I will roughly abstract,
Running time = Number of times the inner loop is executed.

In this equation Knuth has given,
13N + 6A + 5B - 4
'N' I know.
Why 13 N?. 'A' I understand. 'B' I understand.
Why is this 13N + 6A + 5B - 4???

I really need to care about this equation as I proceed? Or My
assumption of
"Running time = Number of times the inner loop is executed" is fair
enough?

Please help.

PS: I understand that it is Out of Topic. But I feel that there is no
better place than comp.lang.c++ to discuss about programming. Please
bear with me.

Jun 27 '08 #1
0 886

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

8 posts views Thread by RickMuller | last post: by
7 posts views Thread by Karin Jensen | last post: by
28 posts views Thread by Bailey.W87 | last post: by
2 posts views Thread by Sugandh Jain | last post: by
7 posts views Thread by apotheos | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.