QSort speed

[Quell]

Hello.
i use qsort, to sort an array of 1000 random integers(from 0-to 10000 each)..and it gives me the result of 0.25 milliseconds....is this a normal time or did i screw up with timing?
thx in advance

[yiannakop]

0.25 milliseconds??? How do you count such a small ammount of time?

[Quell]

i use query performence frequency to do this......
and how about 20 millysecond for bubble sort, same array....

[yiannakop]

Quick sort has time complexity O(nlog(n)) and bubble sort has, O(n^2) though, so for 1000 numbers the quick sort SHOULD (theoretically) be almost 150 times faster than the bubble sort.

[yiannakop]

Ah, and as I can see that (almost) agrees with your results .

[Milano]

Originally posted by Quell
i use query performence frequency to do this......
and how about 20 millysecond for bubble sort, same array....

What is Query Performance Frequency and how to use it ? May I ask ? ^,^

Thanks,

Regards,
-Milano

[Yves M]

Check the Profiling FAQ

[Milano]

Originally posted by Yves M
Check the Profiling FAQ

Thanks Yves a lot,

Regards,

-Milano

[Quell]

Hey.
For my problem above wiht the numbers fo 19 and 0.25 ms...they changed from 6 and 3 ms respectivly...i am not sure what i did and why it happended.....here is a list of changes that i made....
-the speed test is inside of 2 functions....i changed the return type of the functin (from void to double on both).
-i use a parameter list instead of global variables from main.
-i used typdefenition for stuff like unsinged short -> US.
i do wanna change evrything back becuase of amount of code needed to be changed.
Can anyone give me a theoretical unswer to the reason for above change and a little explanation plx.
thx in advance.
P.S. Mialno, the link that was givven has several testes posibiliies...i think that the QueryPerformance counter is the best...becuase the RDSTC(something like that) is not supported on all cpus....and Query is much easier to use.
Just an opinion.

[Milano]

Originally posted by Quell
Hey.
For my problem above wiht the numbers fo 19 and 0.25 ms...they changed from 6 and 3 ms respectivly...i am not sure what i did and why it happended.....here is a list of changes that i made....
-the speed test is inside of 2 functions....i changed the return type of the functin (from void to double on both).
-i use a parameter list instead of global variables from main.
-i used typdefenition for stuff like unsinged short -> US.
i do wanna change evrything back becuase of amount of code needed to be changed.

I amnot quite following you...What exactly are you asking ? Does the speed you mean get faster when there is such a change ? I don't know whether you are implementing qsort algorithm for its complexity purpose only or something else...Are you using it with template for dealing with different runtime types input from the users ?

P.S. Mialno, the link that was givven has several testes posibiliies...i think that the QueryPerformance counter is the best...becuase the RDSTC(something like that) is not supported on all cpus....and Query is much easier to use.
Just an opinion.

Thanks a lot, I see your points here....(lol) Thanks....

-Milano

[Quell]

the above list of changes that i descibed changedd my result on the speed test.
What is the cause of this change?
That is what i was trying to ask before...

[Milano]

First of all, i have to say that I don't have any special skills in compiler optimization techniques, tick counts, hardware architecture such and such, and hence what i posted here might turn out incorrect, and in case if that is true (incorrect), i hope I will be corrected immediately.......:smile:

Originally posted by Quell
-the speed test is inside of 2 functions....i changed the return type of the functin (from void to double on both).

I think the return type's change doesnot mean anything in this case, it won't make any change to your speed, but I think it is a good idea to put your speed test right before and after the operation you want to check. Speed test code must also be executed and that I think also consumes some time.

Originally posted by Quell
-i use a parameter list instead of global variables from main.

About which kinds of variables are to be initialized first in a program, i am not sure, and forgot already ...(lol), true, but I still remember that there is a thread right on this board where galathaea already stated about static variable initialization in a certain program which I think you should do a search for its information. That was a good article I like...

Originally posted by Quell
-i used typdefenition for stuff like unsinged short -> US.

inline_s, define_s are all good for increasing speed of the program...

<I actually intended to post right at the time you posted but I had my dinner waiting...(lol)>

Hope that could be any help,

Regards,
-Milano

[Quell]

hmm...thx for you answer but i am still not sure...what changed the speed of my test? i do not think it is the return type cuz the test is INSIDE the function itself.
and i don't think it is the typedefinition..cuz it just redifines the types....does not slow down/speed up any stuff, does it?
so since my parameters are a bunch of array then they acess time to them will have to change when i put them from global to parameters...but why did one of my time increaaase(bubble sort) and qsort decreased?

[Milano]

Originally posted by Quell
hmm...thx for you answer but i am still not sure...what changed the speed of my test? i do not think it is the return type cuz the test is INSIDE the function itself.

(lol) Are you putting me on ? I mean you went on this way, but why you turn around to look for another way...and ye, the return type does nothing here, i also think so...

and i don't think it is the typedefinition..cuz it just redifines the types....does not slow down/speed up any stuff, does it?

macro defines are always good in some simple cases !!!
This is what I absolutely believe...

so since my parameters are a bunch of array then they acess time to them will have to change when i put them from global to parameters...but why did one of my time increaaase(bubble sort) and qsort decreased?

bubble sort and qsort are absolutely different talks, they have complexities...




-------------------------------------------------------
My signature: i don't like that egg anymore.
No fight is needed from you...

I dreamt i was a turtle trying to get an egg. But there was a kid who stopped me from getting that egg. So i swam at the opposite side of the beach and tricked the kid into following me and them swam to the egg quickly and grabbed it and swam away.
Later that day i needed to take my time even when i felt i hadn't got much time. Then made myself a few extra bucks for taking that time and a weekend job to make more money.

[Ecuador -=[NM]=-]

sorry for this dumb question ( although I heard there ain't stupid questions, just stupid answers ), but doesn't quick sort base on the insertion sort engine ? Well, what I wanted to say is, that I have written several sort engines basing on insertion sort, and phew, used together with vectors this thing is fu... fast. If someone is interested into a piece of code, lemme know...

Greets


ecu@dor