I am trying to see how many steps it will take to sort a set of ints via heap sort.
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)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; }
if x = 500 I get around 3 million
Is this right?
Last edited by Tupcia; 05-17-2008 at 06:19 PM.
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:
pretty much automatically tells you the complexity is (at least) O(n^2).Code:for(int k=x;k>0;k–-){ for(int i=1;i<=k;i++){
I might be wrong.
Quoted more than 1000 times (I hope).Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
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.
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"
