question on qsort library function

[subramanian100in]

What is meant by stable qsort ?

[Richard Tobin]

In article <11************ **********@n33g 2000cwc.googleg roups.com>,
su************* *@yahoo.com, India <su************ **@yahoo.comwro te:

>What is meant by stable qsort ?

A stable sort algorithm is one which leaves unchanged the order of
items that compare equal. C's qsort() is not guaranteed to do this.

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

[CBFalconer]

"su************ **@yahoo.com, India" wrote:

>
What is meant by stable qsort ?

If qsort is implemented via quicksort, it is not stable. Stable
means that equal keys appear in the output in the order in which
they appeared in the input. A stable O(nLOGn) sort is mergesort.

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

[Keith Thompson]

CBFalconer <cb********@yah oo.comwrites:

"su************ **@yahoo.com, India" wrote:

>What is meant by stable qsort ?

If qsort is implemented via quicksort, it is not stable. Stable
means that equal keys appear in the output in the order in which
they appeared in the input. A stable O(nLOGn) sort is mergesort.

There are variants of Quicksort that are stable (at some cost in
speed).

Note that there is no implication in the standard that qsort() is an
implementation of the Quicksort algorithm; it could even be Bubblesort
or Bogosort in a sufficiently perverse implementation. You can
reasonably expect qsort() to use an O(n log n) algorithm. (If you're
curious, you can even investigate its internal behavior by adding
tracing code to your compar() routine.)

(Hmm, I wonder why it's called compar() rather than compare().
Historical reasons, I suppose.)

--
Keith Thompson (The_Other_Keit h) ks***@mib.org <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"

[CBFalconer]

Keith Thompson wrote:

>

.... snip ...

>
(Hmm, I wonder why it's called compar() rather than compare().
Historical reasons, I suppose.)

I suspect the famous 6 char external linkage name limit.

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

[Keith Thompson]

CBFalconer <cb********@yah oo.comwrites:

Keith Thompson wrote:

>>

... snip ...

>>
(Hmm, I wonder why it's called compar() rather than compare().
Historical reasons, I suppose.)

I suspect the famous 6 char external linkage name limit.

Sure, but parameter names don't have external linkage.

--
Keith Thompson (The_Other_Keit h) ks***@mib.org <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"

[Old Wolf]

On Mar 4, 8:57 am, Keith Thompson <[e-mail] ote:

(Hmm, I wonder why it's called compar() rather than compare().
Historical reasons, I suppose.)

Perhaps you could creat a better example?

[Richard Bos]

Keith Thompson <ks***@mib.orgw rote:

CBFalconer <cb********@yah oo.comwrites:

Keith Thompson wrote:

>
(Hmm, I wonder why it's called compar() rather than compare().
Historical reasons, I suppose.)

I suspect the famous 6 char external linkage name limit.

Sure, but parameter names don't have external linkage.

True, but humans are habitual creatures. The habit was to make all
function names in the Standard 6 chars or less; that this wasn't
necessary in the case of a function pointer function parameter did not
manage to break the habit.

Richard

[santosh]

Richard Bos wrote:

Keith Thompson <ks***@mib.orgw rote:

CBFalconer <cb********@yah oo.comwrites:

Keith Thompson wrote:
>>
>(Hmm, I wonder why it's called compar() rather than compare().
>Historical reasons, I suppose.)
>
I suspect the famous 6 char external linkage name limit.

Sure, but parameter names don't have external linkage.

True, but humans are habitual creatures. The habit was to make all
function names in the Standard 6 chars or less; [ ... ]

Since the Standard library is a part of the implementation, it need
not be constrained by the rules of the C standard, isn't it?

[Richard Tobin]

In article <45************ *****@news.xs4a ll.nl>,
Richard Bos <rl*@hoekstra-uitgeverij.nlwr ote:

>(Hmm, I wonder why it's called compar() rather than compare().
Historical reasons, I suppose.)

I suspect the famous 6 char external linkage name limit.

>Sure, but parameter names don't have external linkage.

>True, but humans are habitual creatures. The habit was to make all
function names in the Standard 6 chars or less; that this wasn't
necessary in the case of a function pointer function parameter did not
manage to break the habit.

Does the use of the name "compar" in the standard have any normative
effect at all? Surely implementations are not required to declare it
with that name (since no program can tell the difference)? It seems
to be a purely editorial choice.

-- Richard

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