Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > A question about sort stable

Reply
Thread Tools

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.


 
Reply With Quote
 
 
 
 
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.

 
Reply With Quote
 
 
 
 
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.


 
Reply With Quote
 
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)
 
Reply With Quote
 
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
 
Reply With Quote
 
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"
 
Reply With Quote
 
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.
 
Reply With Quote
 
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.

>
>


 
Reply With Quote
 
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

 
Reply With Quote
 
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

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Stable sort? Hal Fulton Ruby 10 03-24-2005 06:24 AM
Ado sort error-Ado Sort -Relate, Compute By, or Sort operations cannot be done on column(s) whose key length is unknown or exceeds 10 KB. Navin ASP General 1 09-09-2003 07:16 AM
Stable Sort Problem Jon Speer C++ 0 08-26-2003 07:27 PM
stable sort Praveen Kallakuri Perl Misc 1 08-24-2003 05:14 AM
Feature request: stable sort Brian Candler Ruby 1 07-31-2003 05:09 PM



Advertisments