Re: How to prove that a random sort algorithm converges?
- From: "Chip Eastham" <hardmath@xxxxxxxxx>
- Date: 18 May 2006 18:26:08 -0700
James wrote:
In fact, since there can be only a finite number of transpositions, it is
a certainty that the state must converge.
The number of transpositions needed is the number of inversions, which is
why I pushed him toward reasoning about inversions.
However, we need to allow for the possibility of convergence to something
other than the sorted state, since a needed comparison might never be
made.
As above, I fear that gets into weeds the OP doesn't want to visit ;-)
[James:] Not to worry. I will try to understand. The idea of reasoning
about inversions is quite a smart one. Indeed, I am looking for a
simple proof to explain such algorithm so that a lay person can
understand.
As above, I doubt the OP cares about that possibility (although I agree he
needs to understand it-- if only vaguely --in order to grasp why no upper
bound can be given for the number of steps needed to reach the sorted state
whenever the start state has at least 3 elements and at least 1 inversion).
[James:] Actually, I don't really care whether or not to use
probability in the proof, as long as the proof is the easiest for
someone (with little maths background) to understand. The idea of "no
(theoretical) upperbound" for the algorithm is a good point. Now, say
IF I run the algorithm and capture the runtime empirically, and I find
that the runtime appears to scale linearly with respect to increase in
data size n. Can I claim O(n) time complexity for such algorithm?
You will not find that the runtime scales linearly with data size n.
(1) There is no termination criterion in the algorithm. It simply
runs forever without any determination that the array has been
sorted, except for the special cases of n <= 2 (one step).
Iif one keeps track of the actual swaps made, the case of an
of an initially reverse sorted array has a known termintation
(because the actual swaps will reach the theoretical maximum
of n(n-1)/2 of inversions). More generally if one knows the
original number of inversions and tracks the number of actual
swaps, that gives a termination criterion.
(2) The average number of actual swaps over all permutations
is (as Tim Peters said) half the maximum number or n(n-1)/4.
This follows from the fact that the inversions of an array plus
the inversions of the reverse of that array is always n(n-1)/2.
(3) The average number of steps required is greater than the
number of swaps required in proportion to the chances that a
chosen comparison (of adjacent entries) may not result in a
swap. The chance of finding a pair that needs swapping will
on average decrease as the algorithm runs, but it is not a
monotonic decrease and may increase from one step to the
next. An exact computation of the expected number of steps
for any particular permutation of array entries (or for all possible
permutations) can be carried out by means of Markov chains,
and the resulting expected number of steps could then be
averaged over all possible permutations. This is at the level
of a college course in Discrete Mathematics.
regards, chip
.
- Follow-Ups:
- 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?
- From: Tim Peters
- Re: How to prove that a random sort algorithm converges?
- From: Dave Seaman
- 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: Integral table
- Next by Date: Re: manifold cohomology isomorphism
- 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
|
