Re: How to prove that a random sort algorithm converges?
"James" <jamestansc@xxxxxxxxxxxx> wrote in message
news:1147830107.686430.263620@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
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?
Why do you think it does?
.
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) - 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) |
|
