473,327 Members | 1,976 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,327 software developers and data experts.

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 1015

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

8
by: RickMuller | last post by:
I have to sort a list, but in addition to the sorting, I need to compute a phase factor that is +1 if there is an even number of interchanges in the sort, and -1 if there is an odd number of...
7
by: Karin Jensen | last post by:
Hi I am running a PHP program that connects to an Access 2000 database via ODBC: $results = odbc_exec($connection_id, $sql_select); Is it possible to sort the contents of $results? I wish to...
28
by: Bailey.W87 | last post by:
my professor give me this assignment. Sort the R's B's and W's in an array. for example, the user enter: R B W W B B R W W R R W R B W i need to swap the characters in the array and arrange it...
2
by: Clinton Pierce | last post by:
I've filled a DataTable with columns that have custom type (a class that I'm using to keep track of other things, not just a value). When the .Select method goes to sort this column, how do I let...
3
by: kd | last post by:
Hi All, How to perform case-insensitive comparision of strings? Would there be some kind of an indicator, which when set to true, would allow case-insenitive comparision of strings using...
0
by: Brian Henry | last post by:
Here is another virtual mode example for the .NET 2.0 framework while working with the list view. Since you can not access the items collection of the list view you need to do sorting another...
2
by: Sugandh Jain | last post by:
Hi, I want to sort a collection of items on two columns, one after other as it happens for the select query in the Sql server. i.e. Say I have a collection, of Emp ID, designation, salary
7
by: apotheos | last post by:
I can't seem to get this nailed down and I thought I'd toss it out there as, by gosh, its got to be something simple I'm missing. I have two different database tables of events that use different...
11
by: Trent | last post by:
Running this I see that on first run, both bubble and selection sort have 9 sort counts while insertion sort has ZERO. With a sorted list, should this be ZERO for all? Also bsort and Ssort have...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.