C
CBFalconer
Jerry said:
Not so. Extending Quicksort to include multiple fields does not
count. Mergesort remains simple. For an example, look at the
usage examples in hashlib (on my site).
Not so. Extending Quicksort to include multiple fields does not
count. Mergesort remains simple. For an example, look at the
usage examples in hashlib (on my site).
C
CBFalconer
Richard said:
You asked where the misinformation about O(n*n) quicksort
originated. I explained that.
I ignored your query about O(n XOR 2).
J
Juha Nieminen
Pete said:
It is indeed completely valid to say, for example, "insertion sort is
O(n) for sorted arrays". In other words, for all possible inputs which
are already sorted, insertion sort never performs more than n steps. Or
if we put that in different words: There exists no sorted input which
would make insertion sort perform more than n steps.
However, what is "average" input in the case of quicksort? How do you
define it? How does this definition exclude all the inputs which cause
quicksort to perform more steps than (n lg n)?
In order for O(n lg n) to be the true upper bound for quicksort with
average inputs, you would have to define the "average" so that it
excludes those problematic inputs. How do you define it?
If you define it with "any input which does not cause quicksort to
perform more than (n lg n) steps", I think you have a circular
definition here: Of course quicksort is O(n lg n) for all inputs which
quicksort is able to sort in (n lg n) steps.
J
Juha Nieminen
Phil said:
But in that case the given upper bound is incorrect.
Perhaps if you say "quicksort is amortized (n lg n)-time", that might
be closer to the truth.
P
Phil Carmody
Juha Nieminen said:
Bound of _what_? Define _precisely_ what function you are
talking about. It appears you've never heard the concept
of averaging. If so, you're going to be well out of depth
in this thread.
Phil
J
Juha Nieminen
Antoninus said:
Best troll post I have seen in a long time.
P
Phil Carmody
CBFalconer said:
In that case it's O(n^2), and an infinitude of bigger things, too.
Phil
A
Antoninus Twink
Once again, CBF shows that he doesn't have the first inkling of a clue
what he's talking about. Especially stupid since inclusions like
O(n log n) \subset O(n^2)
were the whole *point* of Ben's post...
P
Phil Carmody
Juha Nieminen said:
ARGH! There is not an average input. That's crank speak.
I've seen your type on sci.math, and you'll be talking about
"infinite numbers" or the "probability of a number N being
prime". There is no average input, there's an average over
all inputs (with appropriate weightings, in this case
presumably uniform).
If you are lead to conclusions that seem to not make sense,
then it might just be that your premises and preconceptions
are all messed up.
Phil
A
Antoninus Twink
Why should it exclude them? It AVERAGES OVER all inputs, good and bad
alike. The clue is in the word: AVERAGE.
Depending how anal you want to be about it, fix n, and consider
sequences a[0],...,a[n-1] given as input to some given quicksort
implementation, which we'll assume to be deterministic. Evidently, the
number of steps taken by quicksort depends only on the permutation p of
{0,...,n-1} that corresponds to the order of the a, in the sense that
a[p(0)]< a[p(1)] < ... < a[p(n-1)]. (There are the edge cases when some
of the a's are equal - you can count those too if you care, but I'll
ignore them for simplicity.)
Let Q(a) be the number of steps taken by quicksort with input a.
The worst-case function is
QWC(n) = max{Q(a) | a is a sequence of length n}
(this is a maximum over a finite set by the argument above)
The average-case function is
QAV(n) = 1/n! sum{Q(a(p)) | p is a permutation of {0,...,n-1} and a
corresponds to p in the sense above}.
Now it makes perfect sense to ask whether QWC(n) is in the O(n) class of
functions, and whether QAV(n) is in the O(n) class of functions.
To repeat the definition, which you don't seem to have grasped: f is in
the class O(g) if there is a constant C such that f(n) < C.g(n) for all
n.
What do you mean by "true upper bound"?
B
Ben Bacarisse
You may no read some of the replies you'd had so I will add my own...
Every function that is O(n log n) is also O(n^2). That was my point.
<snip>CBFalconer said:
Every function that is O(n log n) is also O(n^2). That was my point.
J
Juha Nieminen
Richard said:
I fail to see how it does *not* make them obsolete.
Following your definition, "the worst case of insertion sort is
O(n^2)" and "the worst case of of insertion sort is Omega(n^2)" are
completely equivalent statements because both define bounds for the
"worst case of insertion sort" function.
Likewise "the best case of insertion sort is O(n)" and "the best case
of insertion sort is Omega(n)" are also completely equivalent.
Given that they specify upper and lower bounds, those are also
completely equivalent to the big-Theta notation.
In general, we can say "the behavior X for algorithm Y is O(f),
Omega(f) and Theta(f)".
A
Antoninus Twink
That's because you don't understand what they mean, and you refuse to
accept your ignorance and find out.
This is nonsense. They are not equivalent statements, for much the same
reason that "x >= 7" and "x <= 12" are not equivalent statements,
even though they both define bounds for x.
J
Jerry Coffin
[email protected] says... said:
I'm not talking about using multiple fields. With an array, quicksort is
unstable because you partition by scanning from both the beginning
toward the and the end toward the middle, and when you find two elements
out of order with respect to the pivot element, you swap them.
With linked lists, you pick your pivot value and separate your items
into two linked lists (then recursively sort those). Unlike an array,
however, it's trivial to splice new elements to the ends of your linked
lists. Having done that, you get a stable sort.
IMO, the claim elsethread that this is no longer a Quicksort because
it's implemented minutely differently makes little sense. The Quicksort
algorithm consists of:
1) selecting a pivot element
2) partitioning the elementes to be sorted into those less than the
pivot and those greater than the pivot (and those equal end up in one or
the other).
3) recursively sorting each partition.
That's it. Claiming that you have to do the forward and reverse scanning
as Hoare originally did makes no more sense than claiming that it can
only be implemented in languages that existed when he invented it.
J
Juha Nieminen
Antoninus said:
Ok, let me see if I understood correctly. You basically define a
function like:
f1(n) = the average number of steps quicksort performs for all possible
inputs with n elements.
and f1(n) is O(n lg n).
Likewise you could define a function like:
f2(n) = the maximum number of steps quicksort performs for all possible
inputs with n elements.
and in this case f2(n) is O(n^2).
But in this case you can also say that f2(n) is Omega(n^2) and
Theta(n^2) because n^2 is a tight bound for f2.
What would be the function for which you can say "quicksort is
O(n^2) and Omega(n lg n)"?
K
Kai-Uwe Bux
Juha said:
Do you have a reference for that? As far as I know, Big-O notation is rooted
in mathematics and can be used to describe the behavior of any function
(regardless where it comes from).
That is clearly false as Big-O notation is used in many places without
reference to any algorithm whatsoever. It is true that Big-O implies an
upper bound. However, that could be an upper bound, e.g., on best case
space complexity.
No, the definitions of Big-O, Big-Omega, and Big-Theta differ considerably:
If f and g are functions from positive numbers to positive numbers, then
f = O(g) if f(x) < C g(x) for some C>0 and all sufficiently large x
f = Omega(g) if f(x) > C g(x) for some C>0 and all sufficiently large x
f = Theta(g) if c g(x) < f(x) < C g(x) for some c>0 and C>0 and all
sufficiently large x.
However, Big-Theta can be defined in terms of the other two:
f=Theta(g) if and only if f=O(g) and f=Omega(g)
E.g.:
n^2 = O( n^2 )
n^2 = O( n^3 )
n^3 = Omega( n^2 )
n^2 = Theta( n^2 + n )
None of the above has any implications whatsoever about where the functions
involved come from. In particular, any of those can be used to talk about
worst case runtime
avergage case runtime
best case runtime
worst case space
average space
best case space
Best
Kai-Uwe Bux
J
Juha Nieminen
Antoninus said:
By "equivalent" I mean that both are defining the same bounding
function (n^2) and both are valid. My real point was why have an O
notation and an Omega notation, when the Theta notation is telling what
we want? The O and Omega notations seem obsolete.
C
CBFalconer
Ben said:
You are very wrong. In C, n^2 is n XOR 2, and O(n^2) is quite
fast. But, if we use reasonable notation and ask about O(n*n) we
find that to be much slower than O(n log n).
K
Kai-Uwe Bux
Jerry said:
Leaving out the scanning forward and backward part (swapping offending
pairs), you are missing the most important point about quicksort, namely
the one that explains the speed. In terms of number of comparisons,
quicksort is not doing better than, say, heapsort. However, when it comes
to moving elements around in memory, quicksort has a huge advantage.
Experimentally, the number of moves is one place quicksort beats the other
algorithms whereas the number of comparisons is not. Declaring the very
feature of quicksort that makes this happen to be a minor issue seems
weird.
Of course, that only applies to sorting sequences. For linked structures,
the number of pointer operations would be relevant.
Best
Kai-Uwe Bux
B
Ben Bacarisse
CBFalconer said:
Are you just repeating your now rather tired joke? If so, fine, I'll
leave it, but if not, do you really dispute that the time complexity
of merge sort (typically measured as the comparisons made) is also
O(n*n)?