su**************@yahoo.com, India wrote:
>
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 */
--
pete
