Talk About Network

Google


Register and Login
Nick
Password
Register create new account Sign up is FREE and you can post replies, new topics, bookmark posts and more!
Recover lost password


Programming > C++ > A question on S...
Latest [ Topics | Posts ] Archive Post A New Topic Post a Reply
<< Topic < Post Post 1 of 1 Topic 45895 of 47017
Post > Topic >>

A question on Sorting by Comparision Counting

by pvinodhkumar@[EMAIL PROTECTED] May 13, 2008 at 12:10 AM

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.
 




 1 Posts in Topic:
A question on Sorting by Comparision Counting
pvinodhkumar@[EMAIL PROTE  2008-05-13 00:10:23 

Post A Reply:
  Go here to Signup

AddThis Feed Button


About - Advertising - Contact - Frequently Asked Questions - Privacy Policy - Terms of Use - Signup

Contact
tan12V112 Thu Jul 24 16:09:44 CDT 2008.