From: "冷雨" <raincolee@...>
Date: 2010-11-08T04:58:01+09:00
Subject: Re: sort_by is not stable ?

--0016e65b6020a496f004947bec05
Content-Type: text/plain; charset=ISO-8859-1

In fact, python uses Timsort. Java SE and  Android too.
(wikipedia::Timsort <http://en.wikipedia.org/wiki/Timsort>)
It's very efficient, like quicksort.
(btw, quicksort isn't most efficient compare-based sort. see
wikipedia::introsort. <http://en.wikipedia.org/wiki/Introsort>)



On Mon, Nov 8, 2010 at 2:34 AM, John W Higgins <wishdev@gmail.com> wrote:

> 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.
>



-- 
Lai, Yu-Hsuan

--0016e65b6020a496f004947bec05--