470,866 Members | 1,943 Online

# 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()
{
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???

assumption of
"Running time = Number of times the inner loop is executed" is fair
enough?

PS: I understand that it is Out of Topic. But I feel that there is no
0 886 