Velocity Reviews > A question about sort stable

# A question about sort stable

gaoxtwarrior
Guest
Posts: n/a

 03-29-2007
a sort which is stable means it keeps the object's original order. A sort
which is in place is stable. does anyone can explain me what is sort in
place?
thx.

santosh
Guest
Posts: n/a

 03-29-2007
gaoxtwarrior wrote:
> a sort which is stable means it keeps the object's original order. A sort
> which is in place is stable. does anyone can explain me what is sort in
> place?

It means no significant additional storage is used while sorting.

Malcolm McLean
Guest
Posts: n/a

 03-29-2007

"gaoxtwarrior" <(E-Mail Removed)> wrote in message
>a sort which is stable means it keeps the object's original order. A sort
>which is in place is stable. does anyone can explain me what is sort in
>place?
>

Your premise is wrong. qsort() is an sort in place - if you print out the
array as it is sorting you will see values moving up and down within it -
but it is not stable. If Fred fred freddie and Freda all compare equal
because you are doing a case-insensitive comparision of the first four
letters, they will be contigous but in a random order when the sort
finished. A stable sort preserve the order of equal keys.
You can turn qsort into a stable sort by using the index as a tie breaker.

Eric Sosman
Guest
Posts: n/a

 03-29-2007
Malcolm McLean wrote On 03/29/07 15:28,:
> "gaoxtwarrior" <(E-Mail Removed)> wrote in message
>
>>a sort which is stable means it keeps the object's original order. A sort
>>which is in place is stable. does anyone can explain me what is sort in
>>place?
>>

>
> Your premise is wrong. qsort() is an sort in place - if you print out the
> array as it is sorting you will see values moving up and down within it -
> but it is not stable. If Fred fred freddie and Freda all compare equal
> because you are doing a case-insensitive comparision of the first four
> letters, they will be contigous but in a random order when the sort
> finished. A stable sort preserve the order of equal keys.
> You can turn qsort into a stable sort by using the index as a tie breaker.

Just to be clear: That's the "original" index, not the
index that the item happens to occupy at some random moment
during the sort.

--
http://www.velocityreviews.com/forums/(E-Mail Removed)

lawrence.jones@ugs.com
Guest
Posts: n/a

 03-29-2007
santosh <(E-Mail Removed)> wrote:
> gaoxtwarrior wrote:
>> a sort which is stable means it keeps the object's original order. A sort
>> which is in place is stable. does anyone can explain me what is sort in
>> place?

>
> It means no significant additional storage is used while sorting.

Which means it has nothing to do with stability. An in-place sort need
not be stable. In fact, the standard library function qsort() is an
in-place sort, but it's not guaranteed to be stable and most
implementations are not.

-Larry Jones

It's not denial. I'm just very selective about the reality I accept.
-- Calvin

Keith Thompson
Guest
Posts: n/a

 03-29-2007
"Malcolm McLean" <(E-Mail Removed)> writes:
> "gaoxtwarrior" <(E-Mail Removed)> wrote in message
>> a sort which is stable means it keeps the object's original order. A
>> sort which is in place is stable. does anyone can explain me what is
>> sort in place?
>>

> Your premise is wrong. qsort() is an sort in place - if you print out
> the array as it is sorting you will see values moving up and down
> within it -
> but it is not stable.

[...]

I think you're talking about the Quicksort algorithm. The C qsort()
function, declared in <stdlib.h>, may or may not use Quicksort; it's
allowed to use a either a stable or an unstable algorithm.

(I think there are also stable variants of Quicksort, but I don't know
the details.)

--
Keith Thompson (The_Other_Keith) (E-Mail Removed) <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

Richard Tobin
Guest
Posts: n/a

 03-29-2007
In article <(E-Mail Removed)>,
Keith Thompson <(E-Mail Removed)> wrote:

>>> a sort which is stable means it keeps the object's original order. A
>>> sort which is in place is stable. does anyone can explain me what is
>>> sort in place?

>> Your premise is wrong. qsort() is an sort in place - if you print out
>> the array as it is sorting you will see values moving up and down
>> within it -
>> but it is not stable.

>I think you're talking about the Quicksort algorithm. The C qsort()
>function, declared in <stdlib.h>, may or may not use Quicksort; it's
>allowed to use a either a stable or an unstable algorithm.

The other part is true though: qsort() does sort in place, as far as
the input and output are concerned. And qsort() is not guaranteed to
be stable, and isn't in many implementations, so it serves as an
example of an in-place sort which is not necessarily stable.

-- Richard

--
"Consideration shall be given to the need for as many as 32 characters
in some alphabets" - X3.4, 1963.

Richard Harter
Guest
Posts: n/a

 03-29-2007
On Thu, 29 Mar 2007 20:28:35 +0100, "Malcolm McLean"
<(E-Mail Removed)> wrote:

>
>"gaoxtwarrior" <(E-Mail Removed)> wrote in message
>>a sort which is stable means it keeps the object's original order. A sort
>>which is in place is stable. does anyone can explain me what is sort in
>>place?
>>

>Your premise is wrong. qsort() is an sort in place - if you print out the
>array as it is sorting you will see values moving up and down within it -
>but it is not stable. If Fred fred freddie and Freda all compare equal
>because you are doing a case-insensitive comparision of the first four
>letters, they will be contigous but in a random order when the sort
>finished. A stable sort preserve the order of equal keys.
>You can turn qsort into a stable sort by using the index as a tie breaker.

Your description applies to quicksort; IIANM qsort is a library routine
that can be implemented in any old way that the implementor feels like
using, including a stable sort.

>
>

CBFalconer
Guest
Posts: n/a

 03-30-2007
santosh wrote:
> gaoxtwarrior wrote:
>
>> a sort which is stable means it keeps the object's original order.
>> A sort which is in place is stable. does anyone can explain me
>> what is sort in place?

>
> It means no significant additional storage is used while sorting.

Nonsense on the stable. It means items which sort equal appear in
the original order.

--
Chuck F (cbfalconer at maineline dot net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net>

--
Posted via a free Usenet account from http://www.teranews.com

CBFalconer
Guest
Posts: n/a

 03-30-2007
Keith Thompson wrote:
>

.... snip ...
>
> (I think there are also stable variants of Quicksort, but I don't know
> know the details.)

I don't think so, without using auxiliary data (such as indices).
I am prepared to be proven wrong on this.

--
Chuck F (cbfalconer at maineline dot net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net>

--
Posted via a free Usenet account from http://www.teranews.com