# 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?

No, it isn't. What do you mean how many steps? Do you want to count the number of comparisons that heapsort does?

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

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.

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).

Indeed. It seems like you are using one extra unnecessary loop.

It is not heapsort, the code shown is O(n*n*log(n)).
Someone has already posted the same algorithm here once before:
http://cboard.cprogramming.com/showthread.php?t=96847
Read my response from last time.