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


"quasi" <quasi@xxxxxxxx> wrote in message
news:ms3l629ts2t8ruc3ivt4onsn8ved6lacri@xxxxxxxxxx
On 16 May 2006 19:40:16 -0700, "Chris Osborn" <osbornc@xxxxxxxxx>
wrote:

Here's an idea, given n items to sort:

1. Show that eventually the largest element will move to the end.
2. Then recurse on the remaining n-1 items.

That is, the largest item will eventually make it to the end, then
sometime afterward the second largest will make it to its position,
then the third largest to its position, etc...

There's nothing in the statement of the problem that allows you to
assume that if the largest element reaches the end, it will stay
there.

"I swap their position if the value at position i is
greater than the value at position i+1"


.

Relevant Pages