Re: How to prove that a random sort algorithm converges?

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?

.

Relevant Pages

  • Re: How to prove that a random sort algorithm converges?
    ... The number of transpositions needed is the number of inversions, ... upperbound" for the algorithm is a good point. ... runs forever without any determination that the array has been ... (because the actual swaps will reach the theoretical maximum ...
    (sci.math)
  • Re: How to prove that a random sort algorithm converges?
    ... I randomly select a pair of two numbers at adjacient poisitions, ... and I swap their position if the value at position i is ... how do I prove that this algorithm converges? ... I'd try proof by induction on the number of inversions. ...
    (sci.math)
  • Calculate number of (binary) inversions
    ... I'm looking for an algorithm that counts the number of binary ... inversions in thetaor "normal" inversions in nlog. ... A sample for binary inversion: has 4 inversions:, ... programm in Perfect Developer. ...
    (comp.theory)