From: klochner <klochner@...>
Date: 2009-07-13T04:20:05+09:00
Subject: Re: one line sorting

On Jul 11, 6:00 pm, Fabian Streitel <karottenre...@googlemail.com>
wrote:
> 2009/7/11 Haris Bogdanović <fbogdan...@xnet.hr>
>
> > I managed to do selection sort in ruby in one line:
>
> I'm sorry to disappoint you, but that is bubblesort, not selectionsort
> See wikipedia for more information.
>

I'm sorry to disappoint you, but IMHO this behaves more like
selection
sort than bubble sort.  Bubble sort swaps adjacent elements,
"bubbling" the
ith largest (smallest) to the end at iteration i.  If it were bubble
sort
you would see something like if elem[i] < elem[i+1] swap(i,i+1).

Consider the case where the largest element is at the start
of the list, and should be at the other end.  You would get one swap
with this algorithm on the first pass through the list, whereas
bubble
sort would have n-1 swaps in bubbling it into place.

Selection sort swaps the ith largest directly into the ith place on
the ith
iteration, which is what we're seeing here, but rather than store the
index
of the ith largest, he's just swapping any element into position i
that is
larger than the current element.  Same intended result at each
iteration,
with some extra swapping along the way.

I can understand your confusion because Haris is making a lot of
unnecessary
swaps in his implementation, and this extra work does move elements
closer
to their final positions, but there's no bubbling going on.  I'd say
it's
neither selection nor bubble, but clearly n^2.