# of steps in sort

This is a discussion on # of steps in sort within the C++ Programming forums, part of the General Programming Boards category; I am trying to see how many steps it will take to sort a set of ints via heap sort. ...

  1. #1
    Registered User
    Join Date
    Mar 2008
    Posts
    22

    # of steps in sort

    I am trying to see how many steps it will take to sort a set of ints via heap sort.
    Code:
    // x = how many random ints were generated
    int z = 0;
    for(int k=x;k>0;k–-){
        for(int i=1;i<=k;i++){
           item=A[i];
           j=i/2;
           while(j>0 && A[j]<item){
              A[i]=A[j];
              i=j;
              j=j/2;
           }
           z++;     // <------ ****
           A[i]=item;
        }
        temp=A[1];
        A[1]=A[k];
        A[k]=temp;
    }
    When I run it for a set of 100 numbers, I get z (# of operations) around 30,000 ( actualy: 29,534 or 30919 or 30903)
    if x = 500 I get around 3 million


    Is this right?
    Last edited by Tupcia; 05-17-2008 at 06:19 PM.

  2. #2
    Registered User
    Join Date
    Apr 2007
    Location
    Greece
    Posts
    52
    No, it isn't. What do you mean how many steps? Do you want to count the number of comparisons that heapsort does?

  3. #3
    Registered User
    Join Date
    Mar 2008
    Posts
    22
    I am trying to get time complexity ( Big O of N)
    For heap sort it should be O(N*log(N))

    Now I realized that the title of the thread is somewhat missleading

  4. #4
    Registered User
    Join Date
    Apr 2007
    Location
    Greece
    Posts
    52
    This time complexity refers to the number of comparisons. It depends on what implementation of heapsort you have chosen to calculate the theroritial number of comparisons that will have been made at the end of your program.

  5. #5
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Are you sure that what you have is a heap sort? Are you sure the sort works correctly?

    If I'm not mistaken, seeing this:
    Code:
    for(int k=x;k>0;k–-){
        for(int i=1;i<=k;i++){
    pretty much automatically tells you the complexity is (at least) O(n^2).
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  6. #6
    Registered User
    Join Date
    Apr 2007
    Location
    Greece
    Posts
    52
    Indeed. It seems like you are using one extra unnecessary loop.

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,296
    It is not heapsort, the code shown is O(n*n*log(n)).
    Someone has already posted the same algorithm here once before:
    How do I heap sort alphabetically?
    Read my response from last time.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Straight Insertion Sort function problem
    By StaticKyle in forum C++ Programming
    Replies: 6
    Last Post: 05-12-2008, 04:03 AM
  2. Logical errors with seach function
    By Taka in forum C Programming
    Replies: 4
    Last Post: 09-18-2006, 05:20 AM
  3. Folding@Home Cboard team?
    By jverkoey in forum A Brief History of Cprogramming.com
    Replies: 398
    Last Post: 10-11-2005, 08:44 AM
  4. threaded merge sort
    By AusTex in forum Linux Programming
    Replies: 4
    Last Post: 05-04-2005, 04:03 AM
  5. Sorting
    By vasanth in forum A Brief History of Cprogramming.com
    Replies: 12
    Last Post: 11-10-2003, 04:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21