How to prove that a random sort algorithm converges?

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?

.

Relevant Pages

  • 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? ... U.S. Court of Appeals to review three issues ...
    (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? ... you could show that after n trials with k numbers that the probability it is ...
    (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 ... If I do this (random selection and ordering) long enough, ... how do I prove that this algorithm converges? ...
    (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)
  • Re: fast stable sort
    ... With fixed-length records, trivial: Swap randomly-selected record ... Reverse middle records and first record together as unit. ... So Knuth's algorithm only slightly speeds up the process, ... algorithm will assure a fair shuffle, ...
    (comp.programming)
Quantcast