A question on Sorting by Comparision Counting

P

pvinodhkumar

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 <= aKeys[j])
{
++aCountList[j];
}
else
{
++aCountList;
}
}
}

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.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,766
Messages
2,569,569
Members
45,042
Latest member
icassiem

Latest Threads

Top