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

On 17 May 2006 17:43:26 -0700, "James" <jamestansc@xxxxxxxxxxxx>
wrote:

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?

The upper bound is infinity. Just because the probability of
eventually reaching a sorted state is 1, that doesn't mean that there
is an upper bound.

However, for a given starting permutation x, let

E(x) = the expected number of swaps required to sort x.

Questions:

(1) Compute E(x).

(2) Presumably E(x) measures, in some sense, how far from sorted x is.
What feature of x determines E(x)?

(3) In particular, which permutations x maximize E(x)?

(4) What is the average value E_bar of E(x), averaged over all
permutations x? If E_bar can't be computed exactly, approximate it
using a simulation.

quasi
.

Relevant Pages

  • Re: Is C99 the final C? (some suggestions)
    ... thread about who has access to the standard, ... >>Could you provide a reference to the description of the algorithm ... these rare cases) a very loose upper bound. ... > the worst case and say that you only have as much stack space of the ...
    (comp.lang.c)
  • Re: Strategy or Iterator?
    ... private int count; ... Dijkstra's algorithm generates permutations, ... All possible subsequences of length N of the input (considered to be ...
    (comp.lang.java.programmer)
  • Re: how can i large divide?
    ... Big-O notation is a representation of computational complexity, ... Let's say we have an Oalgorithm. ... We should all get in the habit of saying "a Thetaalgorithm" (if ...
    (comp.lang.c)
  • Re: Help with Permutations
    ... >>>In order to keep track of the progress through the algorithm, ... >>>be able to calculate the total number of permutations in advance. ... >> gives 1265, as quasi reported. ... either Maple has a bug or there's a bug in my program. ...
    (sci.math)
  • Re: Permuatations [was: Please Help!!Daughter...]
    ... mathematical purity of exchanging elements. ... ", and then unifies them into a framework based on exchanges), ... It isn't that I don't know how to generate permutations. ... generate-and-discard algorithm with a bit of early pruning). ...
    (comp.lang.java.programmer)