From: John W Higgins <wishdev@...>
Date: 2010-11-08T03:34:57+09:00
Subject: Re: sort_by is not stable ?

--001485f1db9885481d04947ac3f9
Content-Type: text/plain; charset=ISO-8859-1

Good Morning,

On Sun, Nov 7, 2010 at 9:13 AM, Michel Demazure <michel@demazure.com> wrote:

>
> Coming back to the beginning, quicksort correctly coded is stable (cut
> recursively in three parts, with the middle part made by those elements
> equivalent to the choosen pivot).

...

>
> Which means that ruby's is badly coded.
>

The rest of the sane world begs to differ.

http://en.wikipedia.org/wiki/Sorting_algorithm#Quicksort - "...Efficient
implementations of quicksort (with in-place partitioning) are typically
unstable sorts..."

http://perldoc.perl.org/sort.html - "...Mergesort is stable, quicksort is
not..."

http://www.codecogs.com/reference/c/stdlib.h/qsort.php - "...The algorithms
implemented by *qsort*, *qsort_r* and *heapsort* are not stable..."

Linux Man page for qsort - "....If two members compare as equal, their order
in the sorted array is undefined...."

Python in all fairness says they have stable sorts - but they really make no
mention of the algorithm used so I'm unclear as to whether they are using
quicksort at all.

I'd rather have the efficient implementation that one can easily make stable
by using the secondary comparison (as you can easily do in this case) than
an inefficient version that really accomplishes nothing that the efficient
version cannot.

John

P.S. There is nothing in the world stopping anyone from submitting a patch
to add a stable sort option to Ruby. But to pronounce that the hard work of
others is badly coded when it clearly conforms to the normal standard of
multiple mainstream languages is just plain ignorant at best.

--001485f1db9885481d04947ac3f9--