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.