Re: How to prove that a random sort algorithm converges?
- From: "James" <jamestansc@xxxxxxxxxxxx>
- Date: 17 May 2006 17:43:26 -0700
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.
(2) It appears that saying "the algorithm converges is not precise
enough". We need to define what is the convergence criterion.
(3) It also appears that saying "the algorithm converges with
probability 1" is better than saying "the algorithm will converge".
Anyway, what is the difference? Is this an "almost sure" so to speak?
(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?
Any further suggestions?
Thanks
[James]
Tim Peters wrote:
[James]
Supposed I want to sort four numbers {5, 2, 4, 3}
I randomly select a pair of two numbers at adjacient poisitions, say i
and i+1, and I swap their position if the value at position i is
greater than the value at position i+1 (e.g., 5 > 2 so swap their
positions).
If I do this (random selection and ordering) long enough, I would
expect that the numbers are sorted.
My question is: how do I prove that this algorithm converges?
[Tim Peters]
I'd try proof by induction on the number of inversions. An "inversion" is
an index pair <i, j> where i < j and x_i > x_(i+1).
Oops! My mistake: that should say
where i < j and x_i > x_j
The rest wasn't affected by that mistake, simply because the rest had the
correct definition of inversion in mind ;-) Like so:
For example, in your example there are 4 inversions: 5 > 2, 5 > 4,
5 > 3, and 4 > 3.
...
.
- Follow-Ups:
- Re: How to prove that a random sort algorithm converges?
- From: Tim Peters
- Re: How to prove that a random sort algorithm converges?
- From: quasi
- 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?
- Prev by Date: A new algebra appeared named "Concept Algebra"
- Next by Date: "Implied" Probability?
- 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
|
