Re: How to prove that a random sort algorithm converges?
- From: "Tim Peters" <tim.one@xxxxxxxxxxx>
- Date: Wed, 17 May 2006 14:52:37 -0400
[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:
- Prev by Date: Re: Calculus XOR Probability
- Next by Date: Re: Calculus XOR 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
|
