A question on Sorting by Comparision Counting

Collapse
This topic is closed.
X
X
 
  • Time
  • Show
Clear All
new posts
  • pvinodhkumar@gmail.com

    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 SortByComparisi onCount()
    {
    // 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.



Working...