R
Ryan Ply
Ian Collins said:
I must be missing something, looks like a fairly standard quicksort to me.
Ryan -
I must be missing something, looks like a fairly standard quicksort to me.
Ryan -
P
pete
Stephen said:
In this file,
http://www.mindspring.com/~pfilandr/C/e_driver/e_sort.c
the following sorts, are all introspective quicksorts:
itsort
tisort
ti7qsort
qrsort
qisort
A
At_sea_with_C
{snipped}At_sea_with_C said:
Big thanks to everyone in the thread. You guys have given me much food
for thought. I decided to go with Shell sort, for now.
I also looked up the book recommended to me. I did'nt know it was
written by the founders of C! I got a copy. It does look anachronic
compared with the usual 500+ pages computer books, with eye-catching
covers, bundled DVDs and all.
L
Lane Straatman
Interesting. To permute an entire set randomly is quite dramatic. Do thesepete said:
sorts admit of a subset whose order is sufficiently "nice" that one can
select it to survive? If so, then I would derange the other elements
randomly as opposed to permute. The kth element would very likely be either
nice or different. LS
M
mark_bluemel
K & R is an example of how a good textbook doesn't need all that
jazz
I've generally found anything with Brian Kernighan's name on it to be
well-written, concise and worth reading.
C
Chris Dollin
David said:
The Standard C library routine `qsort` need not be a Quicksort implementation.
One just has to hope that QoI issues make it a /decent/ sort implementation,
Tony-Quick or no.
P
pete
Lane said:
itsort, tisort and qisort are foward biased.
First the value of the middle element is swapped with e0.
Then they use an if-else tree to select the median from among
e0, e1, and e(n-1),
and to sort them into place with respect to one another
into this order {1,0,2},
then the first element becomes the pivot
and the other two elements become sorted into their partitions.
ti7qsort and qrsort both use a prng to select
a random element, eR, and to swap it with e0,
before using the if-else tree.
The initial value of eR will then either become the pivot, or
it will be stored in e1 or in e(n-1)
so that the value will be considered during the next partitioning.
If the depth of partitioning becomes twice what
an optimaly ordered array would require for sorting,
then that sets off the heapsort function.
R
Richard Tobin
[/QUOTE]
In the case of qsort(), does the standard anywhere say that the
comparison function can't call qsort()?
-- Richard
C
CBFalconer
Richard said:
The standard says that library routines are not guaranteed to be
re-entrant. That suffices.
--
<http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>
"A man who is right every time is not likely to do very much."
-- Francis Crick, co-discover of DNA
"There is nothing more amazing than stupidity in action."
-- Thomas Matthews
B
Ben Pfaff
In the case of qsort(), does the standard anywhere say that the
comparison function can't call qsort()?[/QUOTE]
Yes. It's a QoI, not a conformance issue. See C99 7.1.4:
4 The functions in the standard library are not guaranteed to be
reentrant and may modify objects with static storage
duration.158)
R
Richard Tobin
Yes. It's a QoI, not a conformance issue. See C99 7.1.4:
4 The functions in the standard library are not guaranteed to be
reentrant and may modify objects with static storage
duration.158)[/QUOTE]
I don't have C99 to hand, but in the C89 standard that sentence occurs
in a section titled "Signals and Interrupts". Has it been explicitly
determined that that sentence is intended to apply to system library
functions simply called recursively, rather than from signal handlers?
-- Richard
B
Ben Pfaff
I don't have C99 to hand, but in the C89 standard that sentence occurs
in a section titled "Signals and Interrupts". Has it been explicitly
determined that that sentence is intended to apply to system library
functions simply called recursively, rather than from signal handlers?[/QUOTE]
In C99 it is nested inside:
7. Library
7.1 Introduction
7.1.4 Use of library functions
R
Richard Tobin
[/QUOTE]
But was it intended to have that effect? Or was it jsut a mistake?
-- Richard
U
user923005
To sort N floats (if float is 4 bytes) takes exactly 5*N passes using
radix sort with radix 256 and 3*N passes with radix 65536.
You make one counting pass, that counts the buckets for each float,
and then one distribution pass that distributes the data.
It is simplified if you transform the data first.
Here are some (architecture specific) sample transformations you can
use in order to use radix on IEEE floating point:
/*
** The proper usage and copyright information for
** this software is covered in DSCRLic.TXT
** This code is Copyright 1999 by Dann Corbit
*/
/*
** This file is INTEL specific. It should be pretty easy to generate
one
** for any sort of architecture.
**
** The whole thing *can* be done generically by using frexp().
** The most important bit is the sign of the number.
** The next most important bit is the sign of the exponent.
** Then comes the exponent magnitude, followed by the mantissa.
** You will need to add the bias to the exponent, so that it becomes
unsigned.
**
** Finally, it would actually be a lot faster to transform the whole
** vector *first* then sort it, then transform it back. Some people
** might be a bit nervous about that, but there is no reason it should
** not work.
**
** Assume typedef's for uint32 and uint64, of the same size and endian-
ness
** as float and double parameters!
** These floating point mapping functions are due to Terje Mathisen.
** They are reprinted with his permission.
*/
#include <assert.h>
#include "inteltyp.h"
#ifdef ASSERT
#undef ASSERT
#endif
#ifdef _DEBUG
#define ASSERT(x) assert((x))
#else
#define ASSERT(x)
#endif
uint32
float2key(float f)
{
uint32 sign,
mant,
mask;
ASSERT(sizeof(float) == sizeof(uint32));
mant = *(uint32 *) & f; /* Load float as array of bits */
sign = mant & SB_MASK32; /* Isolate the leading sign bit */
mant ^= SB_MASK32; /* Invert the sign bit, making + > -
*/
mask = sign - (sign >> 31); /* Either 0 or 0x7fffffff */
mant ^= mask; /* Invert exp and mant if negative */
return mant;
}
uint64
double2key(double d)
{
uint64 sign,
mant,
mask;
ASSERT(sizeof(double) == sizeof(uint64));
mant = *(uint64 *) & d; /* Load float as array of bits */
sign = mant & SB_MASK64; /* Isolate the leading sign bit */
mant ^= SB_MASK64; /* Invert the sign bit, making + > -
*/
mask = sign - (sign >> 63); /* Either 0 or 0x7fffffffffffffff */
mant ^= mask; /* Invert exp and mant if negative */
return mant;
}
The general idea can be used against any floating point type.
You can write your own also, by simply packing the bits in order of
importance for any data type.
E.g., for float, the sign bit of the number is the most important
thing, then the exponent bits and then the mantissa bits.
radix sort with radix 256 and 3*N passes with radix 65536.
You make one counting pass, that counts the buckets for each float,
and then one distribution pass that distributes the data.
It is simplified if you transform the data first.
Here are some (architecture specific) sample transformations you can
use in order to use radix on IEEE floating point:
/*
** The proper usage and copyright information for
** this software is covered in DSCRLic.TXT
** This code is Copyright 1999 by Dann Corbit
*/
/*
** This file is INTEL specific. It should be pretty easy to generate
one
** for any sort of architecture.
**
** The whole thing *can* be done generically by using frexp().
** The most important bit is the sign of the number.
** The next most important bit is the sign of the exponent.
** Then comes the exponent magnitude, followed by the mantissa.
** You will need to add the bias to the exponent, so that it becomes
unsigned.
**
** Finally, it would actually be a lot faster to transform the whole
** vector *first* then sort it, then transform it back. Some people
** might be a bit nervous about that, but there is no reason it should
** not work.
**
** Assume typedef's for uint32 and uint64, of the same size and endian-
ness
** as float and double parameters!
** These floating point mapping functions are due to Terje Mathisen.
** They are reprinted with his permission.
*/
#include <assert.h>
#include "inteltyp.h"
#ifdef ASSERT
#undef ASSERT
#endif
#ifdef _DEBUG
#define ASSERT(x) assert((x))
#else
#define ASSERT(x)
#endif
uint32
float2key(float f)
{
uint32 sign,
mant,
mask;
ASSERT(sizeof(float) == sizeof(uint32));
mant = *(uint32 *) & f; /* Load float as array of bits */
sign = mant & SB_MASK32; /* Isolate the leading sign bit */
mant ^= SB_MASK32; /* Invert the sign bit, making + > -
*/
mask = sign - (sign >> 31); /* Either 0 or 0x7fffffff */
mant ^= mask; /* Invert exp and mant if negative */
return mant;
}
uint64
double2key(double d)
{
uint64 sign,
mant,
mask;
ASSERT(sizeof(double) == sizeof(uint64));
mant = *(uint64 *) & d; /* Load float as array of bits */
sign = mant & SB_MASK64; /* Isolate the leading sign bit */
mant ^= SB_MASK64; /* Invert the sign bit, making + > -
*/
mask = sign - (sign >> 63); /* Either 0 or 0x7fffffffffffffff */
mant ^= mask; /* Invert exp and mant if negative */
return mant;
}
The general idea can be used against any floating point type.
You can write your own also, by simply packing the bits in order of
importance for any data type.
E.g., for float, the sign bit of the number is the most important
thing, then the exponent bits and then the mantissa bits.
U
user923005
That should read:
and then one distribution pass for each radix bucket that distributes
the data.
[snip]
C
CBFalconer
Richard said:
It has to do with not invalidating existing code. And such
routines as strtok.
--
If you want to post a followup via groups.google.com, ensure
you quote enough for the article to make sense. Google is only
an interface to Usenet; it's not Usenet itself. Don't assume
your readers can, or ever will, see any previous articles.
More details at: <http://cfaj.freeshell.org/google/>
R
Richard Tobin
It has to do with not invalidating existing code. And such
routines as strtok.[/QUOTE]
Do you mean existing library implementations? Allowing the comparison
function in qsort() to call qsort() couldn't break any user code.
-- Richard
C
CBFalconer
Richard said:
If qsort is using static memory, it would.
Don't snip attribution lines for material you quote. The
attribution lines are those that say "Foo wrote:" at the beginning.
--
<http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>
"A man who is right every time is not likely to do very much."
-- Francis Crick, co-discover of DNA
"There is nothing more amazing than stupidity in action."
-- Thomas Matthews
U
user923005
On Jan 31, 4:25 pm, (e-mail address removed) (Richard Tobin) wrote:
[snip]
If qsort() calls compare() and compare() calls qsort(), then it will
break things if qsort() is not reentrant.
Not sure why you would want to call qsort() from compare, but that's
neither here nor there.
If (for instance) a lame library qsort() had static read/write
variables in it, all heck would break loose if it was called in a
manner as described above.
[snip]
If qsort() calls compare() and compare() calls qsort(), then it will
break things if qsort() is not reentrant.
Not sure why you would want to call qsort() from compare, but that's
neither here nor there.
If (for instance) a lame library qsort() had static read/write
variables in it, all heck would break loose if it was called in a
manner as described above.
C
Christopher Layne
Ben said:
I cannot possibly take that as being across the board. But then again, it
might just be another case where we've to refer to OS specific manpages. I
thought the rule is that they were reentrant unless otherwise stated as not
required to be reentrant and/or was specifically NOT reentrant (strtok, etc)?
A non-reentrant qsort() would quality as a POS in my book.
Like I said, I wonder if this was applied across the board because of the
outliers - rather than deciding to state it as required unless otherwise
explictly documented.