Re: How to prove that a random sort algorithm converges?
- From: "Tim Peters" <tim.one@xxxxxxxxxxx>
- Date: Tue, 16 May 2006 22:34:54 -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?
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). For example, in your
example there are 4 inversions: 5 > 2, 5 > 4, 5 > 3, and 4 > 3. Prove that
a list is sorted if and only if the number of inversions is 0. Prove that
each step in your algorithm either leaves the number of inversions alone
(when the elements at the position picked are already in order) or reduces
the number of inversions by one (when the elements are swapped). Prove that
if the number of inversions is > 0, then there's at least one pair of
_adjacent_ elements out of order.
Put that all together and you've shown that so long as your list is
unsorted, your algorithm will never increase disorder (will never increase
the number of inversions), and that there's at least one pair of adjacent
elements out of order (because the number of inversions is > 0 so long as
the list is unsorted). The rest depends on exactly what you mean by
"converges" ;-) For example, by your meaning is it true that applying your
algorithm to a list with a single pair of adjacent out-of-order elements
converges? If so, the rest should be easy: it converges when the number of
inversions is 1; assume it converges when the number of inversions is n;
under that assumption, show that it converges when the number of inversions
is n+1.
.
- References:
- Prev by Date: Re: How to prove that a random sort algorithm converges?
- Next by Date: Triangle altitudes intersect
- 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
|
