Hello all,
I have written an ascending sort routine for floats. This seems to do
the job, but for elements over 10,000, it gets awfully slow. A lot of
useless comparisions with previously sorted elements are made. I was
thinking of using a function, that kept an index, to selectively iterate
over unsorted elements. But I am unable to think of a way to do it.
Any ideas to improve the routine and get a better grade?
Thanks to all.
#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX_ALLOC 1000000UL
void sortf_asc(float *a, unsigned long elem) {
int sort_occured = 0;
unsigned long start_offset = 0, current_pos, c1;
float tmp;
while(start_offset < elem - 2) {
for(c1 = 1 + (current_pos = start_offset); c1 < elem; c1++) {
if(a[current_pos] a[c1]) {
tmp = a[c1];
a[c1] = a[current_pos];
a[current_pos] = tmp;
current_pos = c1;
sort_occured = 1;
}
}
if(sort_occured) sort_occured = 0;
else start_offset++;
}
return;
}
int main(int argc, char **argv) {
char *usage = "Usage:\n\nPROGRAM ELEMENTS\n\nELEMENTS - Number of "
"elements to sort, (max. = %lu)\n",
*fopenfail = "Failed to open file.\n",
*tail = NULL;
unsigned long elements = 0, c1;
float *farray = NULL;
FILE *outfp = NULL;
if(argc < 2){ fprintf(stderr, usage, MAX_ALLOC); return EXIT_FAILURE; }
else {
errno = 0;
elements = strtoul(argv[1], &tail, 0);
if(errno == EINVAL || errno == ERANGE) {
fprintf(stderr, usage, MAX_ALLOC);
return EXIT_FAILURE;
}
else if(elements < 2 || elements MAX_ALLOC) {
fprintf(stderr, usage, MAX_ALLOC);
return EXIT_FAILURE;
}
}
farray = malloc(elements * sizeof *farray);
if(!farray) {
fprintf(stderr, "Memory allocation failed.\n");
return EXIT_FAILURE;
}
else {
srand((unsigned int)time(NULL));
for(c1 = 0; c1 < elements; c1++) farray[c1] = (float)rand();
}
outfp = fopen("unsorted", "w");
if(!outfp) {
fprintf(stderr, fopenfail);
free(farray);
return EXIT_FAILURE;
}
else {
for(c1 = 0; c1 < elements; c1++)
fprintf(outfp, "[%lu]: %f\n", c1, farray[c1]);
fclose(outfp);
outfp = NULL;
}
sortf_asc(farray, elements);
outfp = fopen("sorted", "w");
if(!outfp) {
fprintf(stderr, fopenfail);
free(farray);
return EXIT_FAILURE;
}
else {
for(c1 = 0; c1 < elements; c1++)
fprintf(outfp, "[%lu]: %f\n", c1, farray[c1]);
fclose(outfp);
}
return 0;
}
--
Email: The handle, (dot seperated), at gmail dot com. 75 4112
At_sea_with_C said:
Hello all,
I have written an ascending sort routine for floats. This seems to do
the job, but for elements over 10,000, it gets awfully slow. A lot of
useless comparisions with previously sorted elements are made. I was
thinking of using a function, that kept an index, to selectively iterate
over unsorted elements. But I am unable to think of a way to do it.
Any ideas to improve the routine and get a better grade?
You seem to be using Bubble Sort, which is one of the slowest sorts around.
If you are not allowed to call qsort, I suggest taking a look at page 62 of
"The C Programming Language", 2nd edition, by Kernighan and Ritchie, which
implements D L Shell's sorting algorithm. Change int v[] to float v[] -
that should be the only necessary change.
--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999 http://www.cpax.org.uk
email: rjh at the above domain, - www.
Richard Heathfield wrote:
At_sea_with_C said:
>Hello all,
I have written an ascending sort routine for floats. This seems to do the job, but for elements over 10,000, it gets awfully slow. A lot of useless comparisions with previously sorted elements are made. I was thinking of using a function, that kept an index, to selectively iterate over unsorted elements. But I am unable to think of a way to do it.
Any ideas to improve the routine and get a better grade?
You seem to be using Bubble Sort, which is one of the slowest sorts around.
If you are not allowed to call qsort, I suggest taking a look at page 62 of
"The C Programming Language", 2nd edition, by Kernighan and Ritchie, which
implements D L Shell's sorting algorithm. Change int v[] to float v[] -
that should be the only necessary change.
I worked out the logic on paper. We were just told to sort an array of N
integers or floats. I chose floats for no particular reason. It's just
an introductory class, and we haven't covered sorting yet, which is why
I had to think for a while for this one. I will see if the book you
mention is available in our library.
Just one question. Is sorting integers different from sorting floats? In
other words, can I just substitute int for float everywhere in my code
and have it work okay? I can't think why not, but I am just starting C,
so your advice would be helpful.
Thanks for the reply.
--
Email: The handle, (dot seperated), at gmail dot com.
At_sea_with_C said:
Richard Heathfield wrote:
>At_sea_with_C said:
>>Hello all,
I have written an ascending sort routine for floats. This seems to do the job, but for elements over 10,000, it gets awfully slow. A lot of useless comparisions with previously sorted elements are made. I was thinking of using a function, that kept an index, to selectively iterate over unsorted elements. But I am unable to think of a way to do it.
Any ideas to improve the routine and get a better grade?
You seem to be using Bubble Sort, which is one of the slowest sorts around. If you are not allowed to call qsort, I suggest taking a look at page 62 of "The C Programming Language", 2nd edition, by Kernighan and Ritchie, which implements D L Shell's sorting algorithm. Change int v[] to float v[] - that should be the only necessary change.
I worked out the logic on paper.
....and (re)invented Bubble Sort. Lots of us do that. :-) But, as you
discovered, it gets appallingly slow appallingly fast.
We were just told to sort an array of N integers or floats. I chose
floats for no particular reason. It's just
an introductory class, and we haven't covered sorting yet, which is why
I had to think for a while for this one. I will see if the book you
mention is available in our library.
That's a good plan. Or see, for example: http://www.nist.gov/dads/HTML/shellsort.html
Just one question. Is sorting integers different from sorting floats? In
other words, can I just substitute int for float everywhere in my code
and have it work okay? I can't think why not, but I am just starting C,
so your advice would be helpful.
Yes, you can do that.
--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999 http://www.cpax.org.uk
email: rjh at the above domain, - www.
At_sea_with_C wrote, On 30/01/07 12:16:
Richard Heathfield wrote:
>At_sea_with_C said:
>>Hello all,
I have written an ascending sort routine for floats. This seems to do the job, but for elements over 10,000, it gets awfully slow. A lot of useless comparisions with previously sorted elements are made. I was thinking of using a function, that kept an index, to selectively iterate over unsorted elements. But I am unable to think of a way to do it.
Any ideas to improve the routine and get a better grade?
You seem to be using Bubble Sort, which is one of the slowest sorts around. If you are not allowed to call qsort, I suggest taking a look at page 62 of "The C Programming Language", 2nd edition, by Kernighan and Ritchie, which implements D L Shell's sorting algorithm. Change int v[] to float v[] - that should be the only necessary change.
I worked out the logic on paper. We were just told to sort an array of N
integers or floats. I chose floats for no particular reason. It's just
an introductory class, and we haven't covered sorting yet, which is why
I had to think for a while for this one. I will see if the book you
mention is available in our library.
If you are at all serious about C I would recommend buying a copy. I've
been programming in C for over 10 years (and other languages for even
longer) and I still find it a useful reference.
Just one question. Is sorting integers different from sorting floats? In
other words, can I just substitute int for float everywhere in my code
and have it work okay? I can't think why not, but I am just starting C,
so your advice would be helpful.
As long as you don't test for equality (which you do not need to do for
sorting) yes. However, in general I would recommend using double rather
than float except where there is a specific reason for using float. In
most situations when you use a float it will be converted to a double so
using floats can lead to a lot of extra conversions for no real benefit
in most situations.
--
Flash Gordon
"At_sea_with_C" <bl********@dev.null.invalidwrote in message
news:ep**********@aioe.org...
Hello all,
I have written an ascending sort routine for floats. This seems to do the
job, but for elements over 10,000, it gets awfully slow. A lot of useless
comparisions with previously sorted elements are made. I was thinking of
using a function, that kept an index, to selectively iterate over unsorted
elements. But I am unable to think of a way to do it.
Any ideas to improve the routine and get a better grade?
I don't know if you've covered big-O notation yet. You may find this
interesting. http://en.wikipedia.org/wiki/Big_O_notation
The bubble sort is O(N^2), which means that, for example, a sort involving
100,000 records may take 100 times as long as a sort involving 10,000
records. This is as bad as sort algorithms get. Phrased differently, it
does not "scale up" well.
Here is a comparison of sort algorithms: http://en.wikipedia.org/wiki/Sorting_algorithm
Quicksort is considered the best general-purpose sorting algorithm. Unless
the data is ordered very antagonistically, it performs well. As others have
pointed out, it is supported directly by the library.
It would be, of course, instructional for you to implement quicksort
yourself rather than use the library function. This would tend to impress
the instructor if it wasn't assigned.
Now, as far as sorting doubles ...
Floating-point numbers are sortable in the sense that there is a strict
ordering of them -- the computer hardware is always able to determine
unambiguously a<b, a==b, or a>b.
However, the practical difficulty in dealing with floating-point numbers is
that they only approximate real numbers, and so often there are small
residual errors which lead to programming errors by humans.
For example, consider this:
BEGIN
double six=6.0, three=3.0, two=2.0, one=1.0, result1, result2;
result1 = one/two - one/three;
result2 = one/six;
if (result1 == result2) ... /* Danger, Will Robinson! Danger! */
END
1/2 - 1/3 = 1/6, right? Well, not always with computer arithmetic. There
is some inexactness to deal with.
You may find this URL useful: http://www.cygnus-software.com/paper...ringfloats.htm
As far as comparing two floats with a unique ordering -- that is guaranteed.
It is just all the steps leading up to that which cause ambiguity ...
--
David T. Ashley (dt*@e3ft.com) http://www.e3ft.com (Consulting Home Page) http://www.dtashley.com (Personal Home Page) http://gpl.e3ft.com (GPL Publications and Projects)
"David T. Ashley" <dt*@e3ft.comwrites:
Quicksort is considered the best general-purpose sorting algorithm. Unless
the data is ordered very antagonistically, it performs well. As others have
pointed out, it is supported directly by the library.
If by "the library" you mean the standard C library qsort()
function, quicksort is merely a common implementation for
qsort(), not a specified or required algorithm. The GNU libc
implementation, for example, uses merge sort when enough memory
is available.
--
char a[]="\n .CJacehknorstu";int putchar(int);int main(void){unsigned long b[]
={0x67dffdff,0x9aa9aa6a,0xa77ffda9,0x7da6aa6a,0xa6 7f6aaa,0xaa9aa9f6,0x11f6},*p
=b,i=24;for(;p+=!*p;*p/=4)switch(0[p]&3)case 0:{return 0;for(p--;i--;i--)case+
2:{i++;if(i)break;else default:continue;if(0)case 1:putchar(a[i&15]);break;}}}
In article <87************@blp.benpfaff.org>,
Ben Pfaff <bl*@cs.stanford.eduwrote:
>If by "the library" you mean the standard C library qsort() function, quicksort is merely a common implementation for qsort(), not a specified or required algorithm.
It does also explain the "q" in the name.
-- Richard
--
"Consideration shall be given to the need for as many as 32 characters
in some alphabets" - X3.4, 1963.
"David T. Ashley" <dt*@e3ft.comwrote in message
news:wJ******************************@giganews.com ...
"At_sea_with_C" <bl********@dev.null.invalidwrote in message
news:ep**********@aioe.org...
>Hello all,
I have written an ascending sort routine for floats. This seems to do the job, but for elements over 10,000, it gets awfully slow. A lot of useless comparisions with previously sorted elements are made. I was thinking of using a function, that kept an index, to selectively iterate over unsorted elements. But I am unable to think of a way to do it.
Any ideas to improve the routine and get a better grade?
I don't know if you've covered big-O notation yet. You may find this
interesting.
http://en.wikipedia.org/wiki/Big_O_notation
The bubble sort is O(N^2), which means that, for example, a sort involving
100,000 records may take 100 times as long as a sort involving 10,000
records. This is as bad as sort algorithms get. Phrased differently, it
does not "scale up" well.
Here is a comparison of sort algorithms:
http://en.wikipedia.org/wiki/Sorting_algorithm
Quicksort is considered the best general-purpose sorting algorithm.
Unless the data is ordered very antagonistically, it performs well. As
others have pointed out, it is supported directly by the library.
Is there a way where a sort algorithm can ask itself "is this going well?"
and switch gears? For example, could it take a cursory look at the data and
if it doesn't like what it sees, just permute the data randomly? LS
On Jan 30, 6:44 pm, "Lane Straatman" <inva...@invalid.netwrote:
"David T. Ashley" <d...@e3ft.comwrote in messagenews:wJ******************************@gigan ews.com...
Quicksort is considered the best general-purpose sorting algorithm.
Unless the data is ordered very antagonistically, it performs well. As
others have pointed out, it is supported directly by the library.
Is there a way where a sort algorithm can ask itself "is this going well?"
and switch gears? For example, could it take a cursory look at the data and
if it doesn't like what it sees, just permute the data randomly?
Depending on your definition of "take a cursory look at the data and
if it doesn't like what it sees", bogosort could considered. It does
the second part exceptionally well =]
--
WYCIWYG - what you C is what you get
Is there a way where a sort algorithm can ask itself "is this going well?"
and switch gears? For example, could it take a cursory look at the data
and
if it doesn't like what it sees, just permute the data randomly? LS
Yes. That is what David Musser's Introsort does.
Primarily it has been used for implenting C++'s sort() but there is no
reason why it cannot be used for C or even qsort() can be used for it. It
uses quicksort, but if it discovers a portion of the array which is
partitioning badly it switches to heapsort for that portion of the array.
The net result is that this hybrid sort is always guranteed O(N * log N) in
the worse case and gives quicksort like performance in the average case.
See http://en.wikipedia.org/wiki/Introsort
for details.
David Musser also talked about Introselect which is a hybrid version of
quickselect - the algorithm used to find the kth element in an unsorted
array and place it into the kth position. quickselect can also go "bad" and
so Introselect is used to guarantee O(N) behaviour.
Stephen Howe
"Ben Pfaff" <bl*@cs.stanford.eduwrote in message
news:87************@blp.benpfaff.org...
"David T. Ashley" <dt*@e3ft.comwrites:
>Quicksort is considered the best general-purpose sorting algorithm. Unless the data is ordered very antagonistically, it performs well. As others have pointed out, it is supported directly by the library.
If by "the library" you mean the standard C library qsort()
function, quicksort is merely a common implementation for
qsort(), not a specified or required algorithm. The GNU libc
implementation, for example, uses merge sort when enough memory
is available.
Wow. I learn something new every day. I just assumed that qsort was
mnemonic for "quick-sort".
Interestingly enough, *nix and Microsoft documentation seem to differ.
On my *nix box, "man qsort" gets me information that doesn't commit to a
specific algorithm.
However, on Microsoft's website, searching by "qsort" gets me:
<BEGIN>
The qsort function implements a quick-sort algorithm to sort an array of num
elements, each of width bytes.
<END>
which seems to be more committal towards a specific algorithm.
They need to rename the sort function. My suggestions:
faster_than_youre_likely_to_do_it_yourself_sort()
we_might_use_quicksort_and_we_might_not_sort()
dont_ask_whats_in_the_black_box_sort()
--
David T. Ashley (dt*@e3ft.com) http://www.e3ft.com (Consulting Home Page) http://www.dtashley.com (Personal Home Page) http://gpl.e3ft.com (GPL Publications and Projects)
David T. Ashley wrote:
"Ben Pfaff" <bl*@cs.stanford.eduwrote in message
news:87************@blp.benpfaff.org...
>>"David T. Ashley" <dt*@e3ft.comwrites:
>>>Quicksort is considered the best general-purpose sorting algorithm. Unless the data is ordered very antagonistically, it performs well. As others have pointed out, it is supported directly by the library.
If by "the library" you mean the standard C library qsort() function, quicksort is merely a common implementation for qsort(), not a specified or required algorithm. The GNU libc implementation, for example, uses merge sort when enough memory is available.
Wow. I learn something new every day. I just assumed that qsort was
mnemonic for "quick-sort".
Interestingly enough, *nix and Microsoft documentation seem to differ.
On my *nix box, "man qsort" gets me information that doesn't commit to a
specific algorithm.
You may be interested in the Solaris version, reading this you can see
why the algorithm isn't mentioned! http://cvs.opensolaris.org/source/xr...mon/qsort.c#56
--
Ian Collins.
Ben Pfaff wrote:
Ian Collins <ia******@hotmail.comwrites:
>>http://cvs.opensolaris.org/source/xr...mon/qsort.c#56
Eww. Static variables.
Not so bad, they are only used to reduce the number of parameters passed
to the lower level sort routine.
Anyway, what's wrong with using static variables?
--
Ian Collins.
Ian Collins <ia******@hotmail.comwrites:
Ben Pfaff wrote:
>Ian Collins <ia******@hotmail.comwrites:
>>>http://cvs.opensolaris.org/source/xr...mon/qsort.c#56
Eww. Static variables.
Not so bad, they are only used to reduce the number of parameters passed
to the lower level sort routine.
Anyway, what's wrong with using static variables?
They make code non-reentrant, unsafe in the presence of threads,
and generally brittle. Witness strtok, for example.
--
"We put [the best] Assembler programmers in a little glass case in the hallway
near the Exit sign. The sign on the case says, `In case of optimization
problem, break glass.' Meanwhile, the problem solvers are busy doing their
work in languages most appropriate to the job at hand." --Richard Riehle
In article <52*************@mid.individual.net>,
Ian Collins <ia******@hotmail.comwrote:
>Anyway, what's wrong with using static variables?
Isn't qsort() required to be re-entrant? That is, can't the comparison
function call qsort()?
And in many practical environments, qsort() would have to be
thread-safe.
-- Richard
--
"Consideration shall be given to the need for as many as 32 characters
in some alphabets" - X3.4, 1963.
Ben Pfaff wrote:
Ian Collins <ia******@hotmail.comwrites:
>>Ben Pfaff wrote:
>>>Ian Collins <ia******@hotmail.comwrites:
http://cvs.opensolaris.org/source/xr...mon/qsort.c#56
Eww. Static variables.
Not so bad, they are only used to reduce the number of parameters passed to the lower level sort routine.
Anyway, what's wrong with using static variables?
They make code non-reentrant, unsafe in the presence of threads,
and generally brittle. Witness strtok, for example.
Indeed, you are correct. I still had my C++ hat on and was thinking of
static variables as class members, which is nonsense.
I also appear to have posted the wrong link, it should have been http://cvs.opensolaris.org/source/xr...il/qsort.c#110
--
Ian Collins.
In article <52*************@mid.individual.net>,
Ian Collins <ia******@hotmail.comwrote:
>http://cvs.opensolaris.org/source/xr...il/qsort.c#110
That looks a lot more plausible.
Are those ++'s in swapp32() and swapp64() just the result of dumb
cutting-and-pasting? Presumably they get optimised away anyway.
-- Richard
--
"Consideration shall be given to the need for as many as 32 characters
in some alphabets" - X3.4, 1963.
Ian Collins wrote:
Ben Pfaff wrote:
>Ian Collins <ia******@hotmail.comwrites:
http://cvs.opensolaris.org/source/xr...mon/qsort.c#56 Eww. Static variables.
Not so bad, they are only used to reduce the number of parameters
passed to the lower level sort routine.
Anyway, what's wrong with using static variables?
Try re-entering that routine. System routines should be
re-entrant. C doesn't guarantee that.
--
<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
Ian Collins <ia******@hotmail.comwrites:
>
Indeed, you are correct. I still had my C++ hat on and was thinking of
static variables as class members, which is nonsense.
I also appear to have posted the wrong link, it should have been
http://cvs.opensolaris.org/source/xr...il/qsort.c#110
I must be missing something, looks like a fairly standard quicksort to me.
Ryan -
Stephen Howe wrote:
>
Is there a way where a sort algorithm can ask itself
"is this going well?"
and switch gears? For example,
could it take a cursory look at the data and
if it doesn't like what it sees, just permute the data randomly?
LS
>
Yes. That is what David Musser's Introsort does.
Primarily it has been used for implenting C++'s sort() but there is no
reason why it cannot be used for C or even qsort()
can be used for it. It
uses quicksort, but if it discovers a portion of the array which is
partitioning badly it switches to heapsort for that
portion of the array.
The net result is that this hybrid sort is always guranteed
O(N * log N) in
the worse case and gives quicksort like performance in
the average case.
See http://en.wikipedia.org/wiki/Introsort
for details.
David Musser also talked about Introselect which is a hybrid version of
quickselect - the algorithm used to find the kth element in an unsorted
array and place it into the kth position. quickselect can also go "bad" and
so Introselect is used to guarantee O(N) behaviour.
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
--
pete
At_sea_with_C wrote:
Hello all,
{snipped}
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.
:)
--
Email: The handle, (dot seperated), at gmail dot com.
"pete" <pf*****@mindspring.comwrote in message
news:45***********@mindspring.com...
Stephen Howe wrote:
Is there a way where a sort algorithm can ask itself
"is this going well?" and switch gears?
See http://en.wikipedia.org/wiki/Introsort for details.
David Musser also talked about Introselect which is a hybrid version of quickselect - the algorithm used to find the kth element in an unsorted array and place it into the kth position. quickselect can also go "bad" and so Introselect is used to guarantee O(N) behaviour.
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
Interesting. To permute an entire set randomly is quite dramatic. Do these
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
On 31 Jan, 05:58, At_sea_with_C <blindal...@dev.null.invalidwrote:
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.
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.
David T. Ashley wrote:
Quicksort is considered the best general-purpose sorting algorithm. Unless
the data is ordered very antagonistically, it performs well. As others have
pointed out, it is supported directly by the library.
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.
--
Chris "electric hedgehog" Dollin
"A facility for quotation covers the absence of original thought." /Gaudy Night/
Lane Straatman wrote:
>
"pete" <pf*****@mindspring.comwrote in message
news:45***********@mindspring.com...
Stephen Howe wrote:
Is there a way where a sort algorithm can ask itself
"is this going well?" and switch gears?
See http://en.wikipedia.org/wiki/Introsort for details.
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
Interesting. To permute an entire set randomly is quite dramatic.
Do these 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
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.
--
pete
In article <45***************@yahoo.com>,
CBFalconer <cb********@maineline.netwrote:
>Anyway, what's wrong with using static variables?
>Try re-entering that routine. System routines should be re-entrant. C doesn't guarantee that.
In the case of qsort(), does the standard anywhere say that the
comparison function can't call qsort()?
-- Richard
--
"Consideration shall be given to the need for as many as 32 characters
in some alphabets" - X3.4, 1963. ri*****@cogsci.ed.ac.uk (Richard Tobin) writes:
In article <45***************@yahoo.com>,
CBFalconer <cb********@maineline.netwrote:
>>Anyway, what's wrong with using static variables?
>>Try re-entering that routine. System routines should be re-entrant. C doesn't guarantee that.
In the case of qsort(), does the standard anywhere say that the
comparison function can't call qsort()?
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)
--
A competent C programmer knows how to write C programs correctly,
a C expert knows enough to argue with Dan Pop, and a C expert
expert knows not to bother.
In article <87************@blp.benpfaff.org>,
Ben Pfaff <bl*@cs.stanford.eduwrote:
>In the case of qsort(), does the standard anywhere say that the comparison function can't call qsort()?
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)
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
--
"Consideration shall be given to the need for as many as 32 characters
in some alphabets" - X3.4, 1963.
Richard Tobin wrote:
CBFalconer <cb********@maineline.netwrote:
>>Anyway, what's wrong with using static variables?
>Try re-entering that routine. System routines should be re-entrant. C doesn't guarantee that.
In the case of qsort(), does the standard anywhere say that the
comparison function can't call qsort()?
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 ri*****@cogsci.ed.ac.uk (Richard Tobin) writes:
In article <87************@blp.benpfaff.org>,
Ben Pfaff <bl*@cs.stanford.eduwrote:
>>In the case of qsort(), does the standard anywhere say that the comparison function can't call qsort()?
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)
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?
In C99 it is nested inside:
7. Library
7.1 Introduction
7.1.4 Use of library functions
--
"IMO, Perl is an excellent language to break your teeth on"
--Micah Cowan
In article <45***************@yahoo.com>,
CBFalconer <cb********@maineline.netwrote:
>In the case of qsort(), does the standard anywhere say that the comparison function can't call qsort()?
>The standard says that library routines are not guaranteed to be re-entrant. That suffices.
But was it intended to have that effect? Or was it jsut a mistake?
-- Richard
--
"Consideration shall be given to the need for as many as 32 characters
in some alphabets" - X3.4, 1963.
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.
On Jan 31, 11:08 am, "user923005" <dcor...@connx.comwrote:
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.
That should read:
and then one distribution pass for each radix bucket that distributes
the data.
It is simplified if you transform the data first.
[snip]
Richard Tobin wrote:
CBFalconer <cb********@maineline.netwrote:
>>In the case of qsort(), does the standard anywhere say that the comparison function can't call qsort()?
>The standard says that library routines are not guaranteed to be re-entrant. That suffices.
But was it intended to have that effect? Or was it jsut a mistake?
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/>
In article <45***************@yahoo.com>,
CBFalconer <cb********@maineline.netwrote:
>>>In the case of qsort(), does the standard anywhere say that the comparison function can't call qsort()?
>>The standard says that library routines are not guaranteed to be re-entrant. That suffices.
But was it intended to have that effect? Or was it jsut a mistake?
It has to do with not invalidating existing code. And such routines as strtok.
Do you mean existing library implementations? Allowing the comparison
function in qsort() to call qsort() couldn't break any user code.
-- Richard
--
"Consideration shall be given to the need for as many as 32 characters
in some alphabets" - X3.4, 1963.
On Jan 31, 4:25 pm, rich...@cogsci.ed.ac.uk (Richard Tobin) wrote:
[snip]
Do you mean existing library implementations? Allowing the comparison
function in qsort() to call qsort() couldn't break any user code.
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.
Ben Pfaff wrote:
>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?
In C99 it is nested inside:
7. Library
7.1 Introduction
7.1.4 Use of library functions
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.
Richard Tobin wrote:
CBFalconer <cb********@maineline.netwrote:
>>>>In the case of qsort(), does the standard anywhere say that the comparison function can't call qsort()?
The standard says that library routines are not guaranteed to be re-entrant. That suffices.
But was it intended to have that effect? Or was it jsut a mistake?
It has to do with not invalidating existing code. And such routines as strtok.
Do you mean existing library implementations? Allowing the comparison
function in qsort() to call qsort() couldn't break any user code.
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
CBFalconer wrote:
Don't snip attribution lines for material you quote. The
attribution lines are those that say "Foo wrote:" at the beginning.
What different does it make for simple replies? Also, do you not keep a
temporary archive of last posts in your newsreader?
Less crap for me to read - if I'm really interested in WHO wrote something, I
know where to find it. This should be the LEAST important information
pertinent to a response anyways.
Christopher Layne <cl****@com.anodizedwrites:
[reentrancy]
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)?
You may be confusing C with POSIX or SUSv3. C doesn't require
many functions to be reentrant (and doesn't have the concept of
threads), but SUSv3 requires most functions to be thread-safe
(and reentrant) and has an explicit list of functions that need
not be.
--
int main(void){char p[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuv wxyz.\
\n",*q="kl BIcNBFr.NKEzjwCIxNJC";int i=sizeof p/2;char *strchr();int putchar(\
);while(*q){i+=strchr(p,*q++)-p;if(i>=(int)sizeof p)i-=sizeof p-1;putchar(p[i]\
);}return 0;}
Christopher Layne <cl****@com.anodizedwrites:
CBFalconer wrote:
>Don't snip attribution lines for material you quote. The attribution lines are those that say "Foo wrote:" at the beginning.
What different does it make for simple replies? Also, do you not keep a
temporary archive of last posts in your newsreader?
Chuck is particularly sensitive about this kind of thing, but
it's considered kind to preserve attributions.
--
"Large amounts of money tend to quench any scruples I might be having."
-- Stephan Wilms
Ben Pfaff wrote:
Christopher Layne <cl****@com.anodizedwrites:
>CBFalconer wrote:
>>Don't snip attribution lines for material you quote. The attribution lines are those that say "Foo wrote:" at the beginning.
What different does it make for simple replies? Also, do you not keep a temporary archive of last posts in your newsreader?
Chuck is particularly sensitive about this kind of thing, but
it's considered kind to preserve attributions.
For one thing, the attribution allows one to evaluate the validity
of quoted material (in some cases). For example, if it comes from
werty, MI5, or Kenny McCormack it is immediately know to be
worthless. If it comes from Ben Pfaff, Chris Torek, Richard
Heathfield, it is expected to be pertinent. Just sample names that
immediately come to mind, omission (from either list) is not
significant. Inclusion is.
--
<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
Christopher Layne wrote:
CBFalconer wrote:
>Don't snip attribution lines for material you quote. The attribution lines are those that say "Foo wrote:" at the beginning.
What different does it make for simple replies? Also, do you not keep a
temporary archive of last posts in your newsreader?
I don't. Why should I have to?
--
Chris "electric hedgehog" Dollin
"Never ask that question!" Ambassador Kosh, /Babylon 5/
In article <45***************@yahoo.com>,
CBFalconer <cb********@maineline.netwrote:
>Do you mean existing library implementations? Allowing the comparison function in qsort() to call qsort() couldn't break any user code.
If qsort is using static memory, it would.
How could it break user code, rather than the implementation of
qsort()?
>Don't snip attribution lines for material you quote. The attribution lines are those that say "Foo wrote:" at the beginning.
I know what attribution lines are, and I don't see the point of
keeping them all the way back.
-- Richard
--
"Consideration shall be given to the need for as many as 32 characters
in some alphabets" - X3.4, 1963.
In article <11**********************@j27g2000cwj.googlegroups .com>,
user923005 <dc*****@connx.comwrote:
>Do you mean existing library implementations? Allowing the comparison function in qsort() to call qsort() couldn't break any user code.
>If qsort() calls compare() and compare() calls qsort(), then it will break things if qsort() is not reentrant.
Yes, exactly. I'm wondering why the standard didn't require this to
work. Presumably the answer is just that some existing qsort()
implementations (in the 1980s) weren't re-entrant.
>Not sure why you would want to call qsort() from compare, but that's neither here nor there.
It would probably reflect an inefficient design, but there may well be
cases where it's the natural solution.
>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.
As was the case with the ancient Solaris implementation someone posted.
They've fixed it now, but then they've probably made most library
functions re-entrant for thread safety.
-- Richard
--
"Consideration shall be given to the need for as many as 32 characters
in some alphabets" - X3.4, 1963.
Richard Tobin wrote:
In article <45***************@yahoo.com>,
CBFalconer <cb********@maineline.netwrote:
Do you mean existing library implementations? Allowing the
comparison >function in qsort() to call qsort() couldn't break any
user code.
If qsort is using static memory, it would.
How could it break user code, rather than the implementation of
qsort()?
Don't snip attribution lines for material you quote. The
attribution lines are those that say "Foo wrote:" at the beginning.
I know what attribution lines are, and I don't see the point of
keeping them all the way back.
Because it's useful to see who made all the various quoted passages.
Why is it worthwhile deleting them?
Brian
On 1 Feb 2007 11:30:54 GMT, ri*****@cogsci.ed.ac.uk (Richard Tobin)
wrote:
>In article <45***************@yahoo.com>, CBFalconer <cb********@maineline.netwrote:
>>Do you mean existing library implementations? Allowing the comparison function in qsort() to call qsort() couldn't break any user code.
If qsort is using static memory, it would.
How could it break user code, rather than the implementation of qsort()?
>>Don't snip attribution lines for material you quote. The attribution lines are those that say "Foo wrote:" at the beginning.
I know what attribution lines are, and I don't see the point of keeping them all the way back.
There's no point to keeping them all the way back but one should keep
them for any quoted material.
Richard Tobin wrote:
user923005 <dc*****@connx.comwrote:
>>Do you mean existing library implementations? Allowing the comparison function in qsort() to call qsort() couldn't break any user code.
Who wrote the above?
>
>If qsort() calls compare() and compare() calls qsort(), then it will break things if qsort() is not reentrant.
Yes, exactly. I'm wondering why the standard didn't require this
to work. Presumably the answer is just that some existing qsort()
implementations (in the 1980s) weren't re-entrant.
Why do you want to hide the author of the first quote? That is, to
my mind, unethical. In fact it could be considered plagiarism.
--
Chuck F (cbfalconer at maineline dot net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: Casper |
last post by:
Is there features/containers of standard C++ or the STL which will
assist in minimizing memmory fragmentation upon creation of a huge
ammount of objects on the heap?
Currently my application...
|
by: Bing Wu |
last post by:
Hi Folks,
I have a very large table containing 170 million rows of coordinats:
CREATE TABLE "DB2ADMIN"."COORDINATE" (
"FID" INTEGER NOT NULL ,
"AID" INTEGER NOT NULL ,
"X" REAL NOT NULL ,...
|
by: Skybuck Flying |
last post by:
Hi,
I needed a method to determine if a point was on a line segment in 2D. So I
googled for some help and so far I have evaluated two methods.
The first method was only a formula, the second...
|
by: Jéjé |
last post by:
Hi,
hoew can I improve the compilation process of a sharepoint website?
my server is:
2 * P3 Xeom 1ghz
4go ram
2 * 36gb (mirror for OS and website)
2 * 36 Raid 0 (stripping; for temp files...
|
by: Agnes |
last post by:
I had a temp table, I need to pass each invno to a SP to process an update
command .
Now, My client complaint the following process is too slow and take many
times. I really got no idea to...
|
by: Peted |
last post by:
Im using c# 2005 express edition
Ive pretty much finished an winforms application and i need to
significantly improve the visual appeal of the interface.
Im totaly stuck on this and cant seem...
|
by: silentbuddha |
last post by:
Private Sub UserForm_Initialize()
'----------- POPULATE LISTBOX 1 -----------
With ListBox1
.AddItem "--none--"
.AddItem "Account...
|
by: DolphinDB |
last post by:
Tired of spending countless mintues downsampling your data? Look no further!
In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
|
by: ryjfgjl |
last post by:
ExcelToDatabase: batch import excel into database automatically...
|
by: isladogs |
last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM).
In this month's session, we are pleased to welcome back...
|
by: Vimpel783 |
last post by:
Hello!
Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
|
by: ArrayDB |
last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
|
by: Shællîpôpï 09 |
last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
|
by: af34tf |
last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
|
by: Faith0G |
last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome former...
| |