# A question about sort stable

Discussion in 'C Programming' started by gaoxtwarrior, Mar 29, 2007.

1. ### gaoxtwarriorGuest

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.

gaoxtwarrior, Mar 29, 2007

2. ### santoshGuest

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.

santosh, Mar 29, 2007

3. ### Malcolm McLeanGuest

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

Malcolm McLean, Mar 29, 2007
4. ### Eric SosmanGuest

Malcolm McLean wrote On 03/29/07 15:28,:
> "gaoxtwarrior" <> 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.

--

Eric Sosman, Mar 29, 2007
5. ### Guest

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.

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

, Mar 29, 2007
6. ### Keith ThompsonGuest

"Malcolm McLean" <> writes:
> "gaoxtwarrior" <> 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) <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"

Keith Thompson, Mar 29, 2007
7. ### Richard TobinGuest

In article <>,
Keith Thompson <> 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 Tobin, Mar 30, 2007
8. ### Richard HarterGuest

On Thu, 29 Mar 2007 20:28:35 +0100, "Malcolm McLean"
<> wrote:

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

>
>

Richard Harter, Mar 30, 2007
9. ### CBFalconerGuest

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, Mar 30, 2007
10. ### CBFalconerGuest

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

CBFalconer, Mar 30, 2007
11. ### NeluGuest

On Mar 29, 9:32 pm, CBFalconer <> wrote:
> 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.

I was reading through some APIs and came across a description of a
function that was implementing a "non-recursive" quicksort. Does this
mean that it doesn't use recursive calls or does it mean that it
doesn't use a stack at all?

--
Ioan - Ciprian Tandau
tandau _at_ freeshell _dot_ org (hope it's not too late)
(... and that it still works...)

Nelu, Mar 30, 2007
12. ### CBFalconerGuest

Nelu wrote:
> CBFalconer <> wrote:
>> 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.

>
> I was reading through some APIs and came across a description of a
> function that was implementing a "non-recursive" quicksort. Does this
> mean that it doesn't use recursive calls or does it mean that it
> doesn't use a stack at all?

No recursion. The stack, or a reasonable facsimile, is needed.

--
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, Mar 30, 2007
13. ### Keith ThompsonGuest

CBFalconer <> writes:
> 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.

A Google search on "stable quicksort" gets a lot of hits. That's
about all I know on the subject.

--
Keith Thompson (The_Other_Keith) <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"

Keith Thompson, Mar 30, 2007
14. ### NeluGuest

On Mar 30, 12:44 am, CBFalconer <> wrote:
> Neluwrote:
> > CBFalconer <> wrote:
> >> 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.

>
> > I was reading through some APIs and came across a description of a
> > function that was implementing a "non-recursive" quicksort. Does this
> > mean that it doesn't use recursive calls or does it mean that it
> > doesn't use a stack at all?

>
> No recursion. The stack, or a reasonable facsimile, is needed.
>

I thought that maintaining your own stack in an iterative algorithm to
solve a recursively defined problem was also called recursion because
the objects at every step are defined based on the previously saved
objects/states and a recursive call was just a more straightforward
way to define recursion. Is that wrong?

--
Ioan - Ciprian Tandau
tandau _at_ freeshell _dot_ org (hope it's not too late)
(... and that it still works...)

Nelu, Mar 30, 2007
15. ### Eric SosmanGuest

Nelu wrote On 03/30/07 11:08,:
> On Mar 30, 12:44 am, CBFalconer <> wrote:
>
>>Neluwrote:
>>
>>>CBFalconer <> wrote:
>>>
>>>>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.

>>
>>>I was reading through some APIs and came across a description of a
>>>function that was implementing a "non-recursive" quicksort. Does this
>>>mean that it doesn't use recursive calls or does it mean that it
>>>doesn't use a stack at all?

>>
>>No recursion. The stack, or a reasonable facsimile, is needed.
>>

>
>
> I thought that maintaining your own stack in an iterative algorithm to
> solve a recursively defined problem was also called recursion because
> the objects at every step are defined based on the previously saved
> objects/states and a recursive call was just a more straightforward
> way to define recursion. Is that wrong?

The distinction seems less sharp. It's known, after all,
that recursions can be transformed into iterations and vice
versa, so in a sense they can be seen as equivalent. With
that in mind, trying to label a particular algorithm as one
or the other is something of a deliberate inaccuracy.

Here, for example, is an implementation of Euclid's GCD
algorithm:

unsigned int gcd(unsigned int u, unsigned int v) {
return (v == 0) ? u : gcd(v, u % v);
}

I think pretty much anyone would characterize this implementation
as "recursive." But here's another implementation of the very
same algorithm:

unsigned int gcd(unsigned int u, unsigned int v) {
if (v > 0) {
unsigned int r;
while ((r = u % v) != 0) {
u = v;
v = r;
}
}
return u;
}

.... which I think you will agree is "iterative." And yet,
it performs the same calculations and the same tests as the
first! Only the expression has changed, not the algorithm
itself, so I don't think it makes sense to be dogmatic about
saying "This algorithm is recursive!" or "This algorithm is
iterative!"

--

Eric Sosman, Mar 30, 2007
16. ### NeluGuest

On Mar 30, 11:22 am, Eric Sosman <> wrote:
> Nelu wrote On 03/30/07 11:08,:
>
>
>
> > On Mar 30, 12:44 am, CBFalconer <> wrote:

>
> >>Neluwrote:

>
> >>>CBFalconer <> wrote:

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

>
> >>>I was reading through some APIs and came across a description of a
> >>>function that was implementing a "non-recursive" quicksort. Does this
> >>>mean that it doesn't use recursive calls or does it mean that it
> >>>doesn't use a stack at all?

>
> >>No recursion. The stack, or a reasonable facsimile, is needed.

>
> > I thought that maintaining your own stack in an iterative algorithm to
> > solve a recursively defined problem was also called recursion because
> > the objects at every step are defined based on the previously saved
> > objects/states and a recursive call was just a more straightforward
> > way to define recursion. Is that wrong?

>
> The distinction seems less sharp. It's known, after all,
> that recursions can be transformed into iterations and vice
> versa, so in a sense they can be seen as equivalent. With
> that in mind, trying to label a particular algorithm as one
> or the other is something of a deliberate inaccuracy.
>
> Here, for example, is an implementation of Euclid's GCD
> algorithm:
>
> unsigned int gcd(unsigned int u, unsigned int v) {
> return (v == 0) ? u : gcd(v, u % v);
> }
>
> I think pretty much anyone would characterize this implementation
> as "recursive." But here's another implementation of the very
> same algorithm:
>
> unsigned int gcd(unsigned int u, unsigned int v) {
> if (v > 0) {
> unsigned int r;
> while ((r = u % v) != 0) {
> u = v;
> v = r;
> }
> }
> return u;
> }
>
> ... which I think you will agree is "iterative." And yet,
> it performs the same calculations and the same tests as the
> first! Only the expression has changed, not the algorithm
> itself, so I don't think it makes sense to be dogmatic about
> saying "This algorithm is recursive!" or "This algorithm is
> iterative!"

Well, yes and no. In your example (iteration vs. tail recursion) there
is a recursive call but the algorithm does not need to save the state
of its objects. I mean you can make an iteration into a recursive call
but a recursive call may need something extra to be transformed into
an iteration, i.e. tail recursion solution <-> iterative solution;
recursion ->iterative + state stack solution.
I guess my question was whether an iteration that needs to save the
state of it's objects at every step (or in a number of steps
proportional to the number of iteration steps) is a recursion or not.

--
Ioan - Ciprian Tandau
tandau _at_ freeshell _dot_ org (hope it's not too late)
(... and that it still works...)

Nelu, Mar 30, 2007
17. ### Eric SosmanGuest

[OT] Re: A question about sort stable

Nelu wrote On 03/30/07 11:43,:
>
> Well, yes and no. In your example (iteration vs. tail recursion) there
> is a recursive call but the algorithm does not need to save the state
> of its objects. I mean you can make an iteration into a recursive call
> but a recursive call may need something extra to be transformed into
> an iteration, i.e. tail recursion solution <-> iterative solution;
> recursion ->iterative + state stack solution.
> I guess my question was whether an iteration that needs to save the
> state of it's objects at every step (or in a number of steps
> proportional to the number of iteration steps) is a recursion or not.

Somehow I *knew* somebody would mention the magic mantra
of "tail recursion." As if it made a difference ...

All right, if tail recursion bothers you as being somehow
non-recursive, here's the recursion example I hate the most
(because nobody in his right mind would write this code):

long double fib(unsigned int n) {
return n > 1 ? fib(n-1) + fib(n-2) : n > 0;
}

.... which I think you'll agree is recursive, and not tail-
recursive. And here's an iterative expression of the exact
same idea, just done differently (and far more efficiently):

long double fib(unsigned int n) {
long double g = 0, h = 1;
while (n-- > 0) {
long double s = g + h;
g = h;
h = s;
}
return g;
}

Both implementations rely on forming a Fibonacci number as
the sum of the two that precede it; the crux of the method
is the same in both cases even though the implementations
are vastly different. So: Is the computation of Fibonacci
numbers recursive or iterative? My claim is that you can't
assign either label to the algorithm and have the claim
stand beyond debate. It make sense to label implementations
as recursive or iterative, but one is on shaky ground when
saying that a non-recursive implementation is "recursion
in disguise." It can be a false dichotomy.

(There is, of course, a way to compute Fibonacci numbers
without recursion and without iteration, if you grant yourself
the ability to compute powers. Difficult to do accurately
for large n, though.)

(The theory of automata uses "recursively computable"
to cover some of the things we're discussing here, but it's
really not the same notion. It covers a lot of things that
programmers wouldn't think of as recursive: `++i', for
example, is a recursively computable function.)

--

Eric Sosman, Mar 30, 2007
18. ### NeluGuest

On Mar 30, 12:23 pm, Eric Sosman <> wrote:
> Nelu wrote On 03/30/07 11:43,:
>
>
>
> > Well, yes and no. In your example (iteration vs. tail recursion) there
> > is a recursive call but the algorithm does not need to save the state
> > of its objects. I mean you can make an iteration into a recursive call
> > but a recursive call may need something extra to be transformed into
> > an iteration, i.e. tail recursion solution <-> iterative solution;
> > recursion ->iterative + state stack solution.
> > I guess my question was whether an iteration that needs to save the
> > state of it's objects at every step (or in a number of steps
> > proportional to the number of iteration steps) is a recursion or not.

>
> Somehow I *knew* somebody would mention the magic mantra
> of "tail recursion." As if it made a difference ...
>
> All right, if tail recursion bothers you as being somehow
> non-recursive, here's the recursion example I hate the most
> (because nobody in his right mind would write this code):
>
> long double fib(unsigned int n) {
> return n > 1 ? fib(n-1) + fib(n-2) : n > 0;
> }
>

Ok, I'll pretend I am not bothered by the double calculations.

> ... which I think you'll agree is recursive, and not tail-
> recursive.

I do.

> And here's an iterative expression of the exact
> same idea, just done differently (and far more efficiently):
>
> long double fib(unsigned int n) {
> long double g = 0, h = 1;
> while (n-- > 0) {
> long double s = g + h;
> g = h;
> h = s;
> }
> return g;
> }
>

> Both implementations rely on forming a Fibonacci number as
> the sum of the two that precede it; the crux of the method
> is the same in both cases even though the implementations
> are vastly different. So: Is the computation of Fibonacci
> numbers recursive or iterative?

It is recursive in the first case and iterative in the second. The
first case will use a stack to track the status of each call and
you'll have different sizes for the stack at each call. In the second
case, at each iteration step you only track one state throughout the
entire process.

> My claim is that you can't
> assign either label to the algorithm and have the claim
> stand beyond debate. It make sense to label implementations
> as recursive or iterative, but one is on shaky ground when
> saying that a non-recursive implementation is "recursion
> in disguise." It can be a false dichotomy.

What I'm claiming is that if you have an iterative process that uses a
structure (stack or similar) to keep track of the previous states of
the iteration and the size of the structure depends on the number of
iterations steps than that is a recursion.
Your second example doesn't meet this criteria. You have a recursive
implementation and an iterative implementation. However, leaving aside
the double computation in the first example so I don't have to use two
stacks and think too much , an equivalent non-recursive call
implementation could be this:
long fib(unsigned int n) {
struct vector s;
int i;
long res;
for(i=1;i<n;i++) {
}
res=n==0?1:vector_get(s,n-1);
vector_clear(s);
return res;
}
which, I think, is a recursive implementation that doesn't involve a
recursive call because it replaces the call by maintaining the stack/
vector itself.

Your examples show that starting from a recursive definition you may
be able to find an algorithm that can take shortcuts to avoid
recursion but the algorithm is not equivalent, in resource
consumption, to the recursive one, which does extra work (even if
behind the scenes) and requires extra memory.
In the case of quicksort there is no way (at least I don't know of any
way) of implementing an algorithm that uses a fixed number of states
that do not depend on the length of the array that needs to be sorted.

--
Ioan - Ciprian Tandau
tandau _at_ freeshell _dot_ org (hope it's not too late)
(... and that it still works...)

Nelu, Mar 30, 2007
19. ### Malcolm McLeanGuest

"Richard Harter" <> wrote in message
> On Thu, 29 Mar 2007 20:28:35 +0100, "Malcolm McLean"
> <> wrote:
>
>>
>>"gaoxtwarrior" <> 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.
>

Strictly you are right. However if a function called qsort() doesn't
implement quicksort then you ought to send it back.

Malcolm McLean, Mar 30, 2007
20. ### Flash GordonGuest

Malcolm McLean wrote, On 30/03/07 22:05:
> "Richard Harter" <> wrote in message

<snip>

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

> Strictly you are right. However if a function called qsort() doesn't
> implement quicksort then you ought to send it back.

Why if it meets the requirements? Especially as in any decent library it
will be at least as good as a "standard" quicksort implementation for
most uses. If you want a specific algorithm, you can always obtain or
write an implementation.
--
Flash Gordon

Flash Gordon, Mar 30, 2007