Re: QuickSort (worst-cases... special data)

Sem <semyazz@xxxxxxxxx> writes:

Chris F Clark napisał(a):
Sem <semyazz@xxxxxxxxx> writes:

I see i forgot to write that i have to choose always middle element
and both sequences have bad timings, but V is much better than A...
but they are still O(n^2) but different... so again, what can cause it?

Have you tried profiling the code to see where the time is being
spent? If you have two cases that take different amounts of time, I
would think that they would have different execution profiles.

The best thing is that those different timings are correct... (as my
lecturer said, but he didn't said why... ;/ ) So i have to find cause
of this situation...

If your lecturer said the timings are correct, but didn't say why,
then there is something you are supposed to learn from this by
figuring it out for yourself. Look at the various notes from your
course and try to see which if any apply (hint, it is probably in the
most recent notes) or which can be made to apply by looking at things
from a slightly different perspective.

Case in point, I was once learning les Hopital's rule (the one where
taking the derivative shows the value a function converges to). The
lecturer made the point that if that didn't succeed at first,
repeating the process was not the solution. An example of that case
appeared on one of the tests, and I was stumped. I knew what not to
do, but not what to do--I failed to answer that problem. Later, I
discussed the situation with my girlfriend who was also taking the
same course, and she showed me how you could solve the probloem by
substituting a trig identity, in which case the derivative did exist
and the problem solved easily. Hence, I never forgot that technique.
At the same time, I didn't master it, because I never succesfully
solved that problem myself.

Now, I'm not taking your course, so I don't know what might be
relevant (looking at the profile timings was my one suggestion).
However, in this case, it sounds like there is something for you to
learn. For that there is only one solution, work until you learn it.
If the profile timings were relevant and I were your professor, I
would have given the same answer, because your job would be to look at
the profile timings and discover what they are telling you, as in
where do the profile timings for the two different cases differ, and
why do they differ. Of course, if the profile timings weren't
relevant, I might have given the same answer also, because you would
be required to learn that the timings don't contain the answer and
that something else is the key.

Now, if you want to look at the timings, extract some portions and
explain why you think they are relevant or not, then you might get
some more answers. If you think they are relevant, someone may
confirm it, and you can focus on the why they are relevant. If you
think they are not relevant and explain why, someone may confirm (or
correct) your reasoning.

Sorry, I can't be more help, but we readers aren't omniscient and
omnipotent, and so we cannot see what you are supposed to learn and
magically insert the solution into your head. The more you work
through the problem yourself and if necessary post you attempts, the
more you will learn from it.

Chris
.