Re: How to prove that a random sort algorithm converges?
- From: "Tim Peters" <tim.one@xxxxxxxxxxx>
- Date: Wed, 17 May 2006 21:39:32 -0400
[James]
Thanks to all who contributed in one way or another.
Although I will need sometime to digest your suggestions, there are a
few things I learn at the moment:
(1) There are more than one way to prove the algorithm.
That's true. The way I suggested is the easiest of all those I saw,
although it also gives the least information.
(2) It appears that saying "the algorithm converges is not precise
enough". We need to define what is the convergence criterion.
Well, "converges" has no conventional meaning here at all, so you have to
define what you mean. Convergence usually applies to iterative numerical
algorithms, such as talking about how quickly a root-finding algorithm can
be expected to converge to a root to within a given tolerance.
It appears that what you want to know is whether your algorithm
_terminates_, but there was no termination criterion given. People are
reasonably guessing that you intend for your algorithm to terminate when the
list reaches a wholly sorted state.
(3) It also appears that saying "the algorithm converges with
probability 1" is better than saying "the algorithm will converge".
Not really, unless _you_ define "convergence" in terms of probability.
Anyway, what is the difference? Is this an "almost sure" so to speak?
See next point.
(4) Although the algorithm may look silly on the first sight, but it is
much hard to show its runtime complexity as compared to a proper bubble
sort. Is there a way to find the upper bound?
Yes: if the list isn't sorted at the start and has at least 3 elements,
there is no finite upper bound. You only need to consider this special case
to see that:
2 1 3
The first step of your algorithm has to pick one of these two pairs:
2 1
1 3
If the first step picks 2 1, the list is changed to
1 2 3
and the algorithm (presumably) terminates. If it picks 1 3 instead, the
list isn't changed, and you stay in the same state.
If choices are made randomly, and the probability of picking "2 3" is 1/2,
then the probability of picking "2 3" n times in a row is (1/2)^n (a half
raised to the power of n). That's also the probability that the algorithm
has not terminated after n steps. (1/2)^n is strictly greater than 0 for
any finite n, so there is no upper bound on how many steps the algorithm
_may_ require, even in this simple case of a 3-number list with a single
inversion.
Nevertheless, (1/2)^n _approaches_ zero quickly as n increases, and you have
a much higher chance of being killed by lightning tomorrow than that the
algorithm in the simple case above wouldn't terminate after (say) 64 steps.
If the list is sorted at the start, then there's an upper bound of 0 steps.
If the list has two elements, then one step is an upper bound (there's only
1 pair you _can_ pick then, and if it's out of order the first step will
complete sorting the list; OTOH, if it was already in order, there is no
first step).
.
- Follow-Ups:
- Re: How to prove that a random sort algorithm converges?
- From: Dave Seaman
- Re: How to prove that a random sort algorithm converges?
- References:
- Re: How to prove that a random sort algorithm converges?
- From: Tim Peters
- Re: How to prove that a random sort algorithm converges?
- From: James
- Re: How to prove that a random sort algorithm converges?
- Prev by Date: Re: Difference between an "independent set" and a "maximal independent set"
- Next by Date: Re: Difference between an "independent set" and a "maximal independent set"
- Previous by thread: Re: How to prove that a random sort algorithm converges?
- Next by thread: Re: How to prove that a random sort algorithm converges?
- Index(es):
Relevant Pages
|
