question on qsort library function

[subramanian100in]

What is meant by stable qsort ?

 

[CBFalconer]

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.

 

[Richard Tobin]

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

 

[Keith Thompson]

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

 

[CBFalconer]

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

 

[Keith Thompson]

I suspect the famous 6 char external linkage name limit.

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

 

[Old Wolf]

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

Perhaps you could creat a better example?

 

[Richard Bos]

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]

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]

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

[/QUOTE]

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

 

[Richard Heathfield]

Richard Tobin said:

Does the use of the name "compar" in the standard have any normative
effect at all?

No, none whatsoever.

 

[Richard Bos]

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

It seems to be a purely editorial choice.[/QUOTE]

Yes, but one probably born from habit.

Richard

 

[Richard Tobin]

I suspect the famous 6 char external linkage name limit.

[/QUOTE]

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

I looked up qsort in successively older Unix manuals, and the answer
appears to be that it's called compar() because it *did* originally
have external linkage. In third edition Unix, the qsort() function
did not take an argument for the comparison function, it just called
compar(). A default version of compar() was provided in the library
which did a byte-by-byte comparison. At that time the functions were
written in assembler, but C almost certainly inherited the name.

-- Richard

 

[Guest]

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.[/QUOTE]

Programs can tell the difference by defining compar as a macro which
would cause a syntax error, before including the standard header.
Because of this (and the fact that compar is not a reserved name),
implementations are not even allowed to use compar as a parameter name.

 

[pete]

What is meant by stable qsort ?

/* BEGIN output from pt_sort.c */

Arrays of type char *,
are being sorted by string length.

This is the original order of the test array:
one
two
three
four
five
six
seven
eight
nine
ten

Stable insertionsort:
one
two
six
ten
four
five
nine
three
seven
eight

Nonstable simple selection sort;
four is after nine, and three is after eight:
one
two
six
ten
five
nine
four
eight
three
seven

Standard library qsort, unspecified ordering of equal keys:
six
two
one
ten
five
nine
four
eight
seven
three

/* END output from pt_sort.c */

/* BEGIN pt_sort.c */

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define SORT_FUNCTIONS { \
no_sort, "This is the original order of the test array:",\
i_sort, "Stable insertionsort:", \
slsort, "Nonstable simple selection sort;\nfour is " \
"after nine, and three is after eight:", \
qsort, "Standard library qsort, " \
"unspecified ordering of equal keys:" \
}
#define NUMBERS { \
"one", "two","three","four","five", \
"six","seven","eight","nine", "ten" \
}
#define NMEMB (sizeof numbers / sizeof *numbers)
#define SORTS (sizeof s_F / sizeof *s_F)

int lencomp(const void *, const void *);
void no_sort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *));
void i_sort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *));
void slsort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *));

int main(void)
{
size_t element, sort;
struct sf {
void (*function)(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *));
const char *description;
} s_F[] = SORT_FUNCTIONS;
const char *numbers[] = NUMBERS;
char *copy[NMEMB];

puts("/* BEGIN output from pt_sort.c */\n\nArrays of type "
"char *,\nare being sorted by string length.");
for (sort = 0; sort != SORTS; ++sort) {
putchar('\n');
puts(s_F[sort].description);
memcpy(copy, numbers, sizeof copy);
s_F[sort].function(copy, NMEMB, sizeof *copy, lencomp);
for (element = 0; element != NMEMB; ++element) {
puts(copy[element]);
}
}
puts("\n/* END output from pt_sort.c */");
return 0;
}

int lencomp(const void *a, const void *b)
{
const size_t a_len = strlen(*(const char **)a);
const size_t b_len = strlen(*(const char **)b);

return b_len > a_len ? -1 : b_len != a_len;
}

void no_sort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *))
{
base, nmemb, size, compar;
}

void i_sort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *))
{
unsigned char *array, *high, *low, *p1, *p2, *end, swap;

if (nmemb-- > 1) {
array = base;
do {
low = array;
array += size;
high = array;
while (compar(low, high) > 0) {
p1 = low;
p2 = high;
end = p2 + size;
do {
swap = *p1;
*p1++ = *p2;
*p2++ = swap;
} while (p2 != end);
if (low == base) {
break;
}
high = low;
low -= size;
}
} while (--nmemb != 0);
}
}

void slsort(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *))
{
size_t tail;
unsigned char *array, *first, *middle, *p1, *p2, *end, swap;

for (array = base; nmemb-- > 1; array += size) {
first = middle = array + size;
tail = nmemb;
while (--tail != 0) {
middle += size;
if (compar(first, middle) > 0) {
first = middle;
}
}
if (compar(array, first) > 0) {
p1 = array;
p2 = first;
end = p2 + size;
do {
swap = *p1;
*p1++ = *p2;
*p2++ = swap;
} while (p2 != end);
}
}
}

/* END pt_sort.c */