473,320 Members | 2,035 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

How to improve this sort?

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.
Jan 30 '07 #1
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.
Jan 30 '07 #2
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.
Jan 30 '07 #3
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.
Jan 30 '07 #4
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
Jan 30 '07 #5
"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)
Jan 30 '07 #6
"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;}}}
Jan 30 '07 #7
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.
Jan 30 '07 #8

"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
Jan 30 '07 #9
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

Jan 30 '07 #10
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
Jan 30 '07 #11
"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)
Jan 30 '07 #12
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.
Jan 30 '07 #13
Ian Collins <ia******@hotmail.comwrites:
http://cvs.opensolaris.org/source/xr...mon/qsort.c#56
Eww. Static variables.
--
"It wouldn't be a new C standard if it didn't give a
new meaning to the word `static'."
--Peter Seebach on C99
Jan 30 '07 #14
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.
Jan 30 '07 #15
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
Jan 30 '07 #16
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.
Jan 30 '07 #17
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.
Jan 30 '07 #18
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.
Jan 30 '07 #19
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
Jan 31 '07 #20
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 -
Jan 31 '07 #21
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
Jan 31 '07 #22
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.
Jan 31 '07 #23

"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
Jan 31 '07 #24
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.

Jan 31 '07 #25
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/

Jan 31 '07 #26
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
Jan 31 '07 #27
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.
Jan 31 '07 #28
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.
Jan 31 '07 #29
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.
Jan 31 '07 #30
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
Jan 31 '07 #31
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
Jan 31 '07 #32
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.
Jan 31 '07 #33
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.

Jan 31 '07 #34
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]

Jan 31 '07 #35
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/>
Jan 31 '07 #36
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.
Feb 1 '07 #37
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.
Feb 1 '07 #38
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.
Feb 1 '07 #39
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

Feb 1 '07 #40
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.

Feb 1 '07 #41
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;}
Feb 1 '07 #42
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
Feb 1 '07 #43
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
Feb 1 '07 #44
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/

Feb 1 '07 #45
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.
Feb 1 '07 #46
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.
Feb 1 '07 #47
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
Feb 1 '07 #48
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.
Feb 1 '07 #49
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>
Feb 2 '07 #50

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

4
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...
7
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 ,...
65
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...
6
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...
1
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...
11
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...
0
by: silentbuddha | last post by:
Private Sub UserForm_Initialize() '----------- POPULATE LISTBOX 1 ----------- With ListBox1 .AddItem "--none--" .AddItem "Account...
0
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...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
1
isladogs
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...
0
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...
0
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...
1
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....
0
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
0
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...
0
isladogs
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...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.