K&R has three different versions of qsort, and the ultimate one is supposed
to be like the one in the std library. I'm trying to implement the first,
which is in §4.10.
I think I'm pretty close with this:
void qsort(int v[], int left, int right)
{
int i, last;
void swap(int v[], int i, int j);
if (left >= right)
return;
swap (v, left, (left + right)/2);
last = left;
for (i = left+ 1; i <= right; i++)
if (v[i] < v[left])
swap (v, ++last, i);
swap(v, left, last);
qsort(v, left, last - 1);
qsort(v, last + 1, right);
}
void swap(int v[], int i, int j)
{
int temp;
temp = v[i];
v[i] = v[j];
v[j] = temp;
}
#include <stdio.h>
#define size 9
int main(void)
{
int m[size], i;
for (i=0; i < size; ++ i)
{
m[i] = i - size;
printf(" %d \n ", m[i]);
}
qsort (m[], 0, size - 1);
for (i=0; i < size; ++ i) printf(" %d \n ", m[i]);
return 0;
}
// gcc -o sort c5.c
gcc objects with:
F:\gfortran\sou rce>gcc -o sort c5.c
c5.c: In function 'main':
c5.c:42: error: expected expression before ']' token
If I count correctly, this is the qsort call. I'm not surprised that gcc
objects, as I'm not sure about this syntax at all.
I guess that's question one. The other is how to call the stdlib version
of qsort, whose syntax is given in appdx B5:
void qsort(void *base, size_t n, size_t size,
int (*cmp)(const void *, const void *)
Beautiful night here in New Mexico. I can hear and even smell the state
fair. cheers,
--
We are here and it is now. Further than that, all human knowledge is
moonshine. 3
H. L. Mencken
61  5854 
Hi Ron,
made few changes and it worked. :)
< changes
Yours
diff qsort_samp.c original_qsort. c
1,3d0
< #include <stdio.h>
< #define size 9
<
32a30,32
#include <stdio.h>
#define size 9
39c39
< m[i] = size - i;
---
m[i] = i - size;
43c43
< qsort (m, 0, size - 1);
---
qsort (m[], 0, size - 1);
Regards,
Dhilip
On 9 Sep, 06:30, Ron Ford <r...@example.i nvalidwrote:
K&R has three different versions of qsort, and the ultimate one is supposed
to be like the one in the std library.
note the calling interafec may be similar but the guts don't
have to be. qsort() does not have to implement Quick Sort.
*I'm trying to implement the first,
which is in §4.10.
I don't understand "trying to implement". Why not copy the code
provided.
I think I'm pretty close with this:
void qsort(int v[], int left, int right)
{
* int i, last;
* void swap(int v[], int i, int j);
* if (left >= right)
* * return;
* swap (v, left, (left + right)/2);
* last = left;
* for (i = left+ 1; i <= right; i++)
* * if (v[i] < v[left])
* * * swap (v, ++last, i);
* * swap(v, left, last);
* * qsort(v, left, last - 1);
* * qsort(v, last + 1, right);
}
void swap(int v[], int i, int j)
{
* int temp;
* temp = v[i];
* v[i] = v[j];
* v[j] = temp;
} *
that looks identical to K&R (except you stripped the comments)
#include <stdio.h>
#define size 9
int main(void)
{
* int m[size], i;
* for (i=0; i < size; ++ i)
* * {
* * * * m[i] = i - size;
* * * * printf(" %d \n ", m[i]);
* * }
* qsort (m[], 0, size - 1);
go and reread about arrays. eg K&R page 29
>
* for (i=0; i < size; ++ i) *printf(" %d \n ", m[i]);
* return 0;
}
// gcc -o sort c5.c
gcc objects with:
F:\gfortran\sou rce>gcc -o sort c5.c
c5.c: In function 'main':
c5.c:42: error: expected expression before ']' token
If I count correctly, this is the qsort call. *I'm not surprised that gcc
objects, as I'm not sure about this syntax at all.
good. because it's wrong
I guess that's question one. *The other is how to call the stdlib version
of qsort, whose syntax is given in appdx B5:
void qsort(void *base, size_t n, size_t size,
* * * * * *int (*cmp)(const void *, const void *)
Beautiful night here in New Mexico. *I can hear and even smell the state
fair. *cheers,
horrid morning here in Xshire. It's precipitating it down.
--
Nick Keighley
C++: "an octopus made by nailing extra legs onto a dog"
-- Steve Taylor, 1998
On Tue, 9 Sep 2008 01:14:50 -0700 (PDT), s.***********@g mail.com posted:
Hi Ron,
made few changes and it worked. :)
< changes
>Yours
diff qsort_samp.c original_qsort. c
1,3d0
< #include <stdio.h>
< #define size 9
<
32a30,32
>#include <stdio.h>
#define size 9
39c39
< m[i] = size - i;
---
> m[i] = i - size;
43c43
< qsort (m, 0, size - 1);
---
> qsort (m[], 0, size - 1);
Regards,
Dhilip
Thanks for your response, Phil. Removing the braces from m in the qsort
call and reversing i and size while populating m gives me the output I was
looking for:
F:\gfortran\sou rce>sort
9
8
7
6
5
4
3
2
1
1
2
3
4
5
6
7
8
9
--
We are here and it is now. Further than that, all human knowledge is
moonshine. 3
H. L. Mencken
On Tue, 9 Sep 2008 01:28:09 -0700 (PDT), Nick Keighley posted:
On 9 Sep, 06:30, Ron Ford <r...@example.i nvalidwrote:
>K&R has three different versions of qsort, and the ultimate one is supposed
to be like the one in the std library.
note the calling interafec may be similar but the guts don't
have to be. qsort() does not have to implement Quick Sort.
I think there's two issues here. An implementation could modify the call
to qsort. Chris Torek says this about that:
%- That said, I do not know of any C implementations that modify calls
%- to qsort(). Of course, this does not guarantee that none exist.
%- (Among other things, to cross comp.lang.c threads a bit, I have
%- never seen or used a [full] C99 implementation. Perhaps one of
%- those -- several are rumored to exist -- might substitute some
%- qsort() calls, for instance.
Or, the qsort in the library might not be a quicksort. Where can I look to
see the source for a gcc install? A search with qsort*.* only turns up a
forbidding-looking creature called qsort_c_module:
GFORTRAN module created from freeformat50.f9 5 on Wed Aug 27 17:16:03 2008
MD5:2948eeeeb93 405ec66df04faa2 275dfe -- If you edit this, you'll get what
you deserve.
(() () () () () () () () () () () () () () () () () () () () () () () ()
() () ())
()
()
()
()
(2 'qsort_c_module ' 'qsort_c_module ' 'qsort_c_module ' 1 ((MODULE
UNKNOWN-INTENT UNKNOWN-PROC UNKNOWN UNKNOWN) (UNKNOWN 0 0 0 UNKNOWN ())
0 0 () () 0 () () 0 0)
3 'qsortc' 'qsort_c_module ' 'qsortc' 1 ((PROCEDURE UNKNOWN-INTENT
MODULE-PROC DECL UNKNOWN SUBROUTINE RECURSIVE ALWAYS_EXPLICIT ) (UNKNOWN
0 0 0 UNKNOWN ()) 4 0 (5) () 0 () () 0 0)
5 'a' '' 'a' 4 ((VARIABLE INOUT UNKNOWN-PROC UNKNOWN UNKNOWN DIMENSION
DUMMY) (INTEGER 8 0 0 INTEGER ()) 0 0 () (1 ASSUMED_SHAPE (CONSTANT (
INTEGER 4 0 0 INTEGER ()) 0 '1') ()) 0 () () 0 0)
)
('qsort_c_modul e' 0 2 'qsortc' 0 3)
! end excerpt
>
>*I'm trying to implement the first,
which is in §4.10.
I don't understand "trying to implement". Why not copy the code
provided.
snip
that looks identical to K&R (except you stripped the comments)
I'll be the first to own up to speaking elliptically on occasion. I don't
see it there.
go and reread about arrays. eg K&R page 29
I leafed through pp25-100 and didn't see it.
>If I count correctly, this is the qsort call. *I'm not surprised that gcc
objects, as I'm not sure about this syntax at all.
good. because it's wrong
No, it was the brackets on m in the qsort call that was the culprit on line
42.
--
We are here and it is now. Further than that, all human knowledge is
moonshine. 3
H. L. Mencken
"Ron Ford" <ro*@example.in validwrote in message
Or, the qsort in the library might not be a quicksort. Where can I look
to
see the source for a gcc install? A search with qsort*.* only turns up a
forbidding-looking creature called qsort_c_module:
That's typical. Bread and butter code is written portably and with an
emphasis on readability and maintainablilit y (in an ideal world). Libraries
are written for speed, often using many platform-dependent shortcuts.
However there are plenty of implementations of the quicksort algorithm on
the web. The main thing to remember is to use the same interface as the
stdlib function. This is a bit of extra work, but the added generality is
worth it.
--
Free games and programming goodies. http://www.personal.leeds.ac.uk/~bgy1mm
Malcolm McLean wrote, On 09/09/08 21:38:
>
"Ron Ford" <ro*@example.in validwrote in message
>Or, the qsort in the library might not be a quicksort. Where can I
look to
see the source for a gcc install? A search with qsort*.* only turns up a
forbidding-looking creature called qsort_c_module:
gcc in general uses whatever library the system happens to provide. So
you need to be more specific and also address the question to a
group/list dedicated to your implementation.
That's typical. Bread and butter code is written portably and with an
emphasis on readability and maintainablilit y (in an ideal world).
Not sure what you mean by "bread and butter code" here.
Libraries are written for speed, often using many platform-dependent
shortcuts.
True.
However there are plenty of implementations of the quicksort algorithm
on the web.
Yes, but quicksort is not necessarily the best algorithm to use.
The main thing to remember is to use the same interface as
the stdlib function. This is a bit of extra work, but the added
generality is worth it.
Whether you want to use the same interface or something different
depends on what you want to achieve.
--
Flash Gordon
On Tue, 09 Sep 2008 22:19:58 +0100, Flash Gordon posted:
>> Where can I
look to
see the source for a gcc install?
gcc in general uses whatever library the system happens to provide. So
you need to be more specific and also address the question to a
group/list dedicated to your implementation.
I asked for more info in gnu.gcc.help.
The part I don't get right now is why the call to qsort worked without
#include <stdlib.h>
?
--
What men value in this world is not rights but privileges. 7
H. L. Mencken
Ron Ford <ro*@example.in validwrites:
[...]
The part I don't get right now is why the call to qsort worked without
#include <stdlib.h>
?
Luck (arguably bad luck).
In C90, if you call a function with no visible declaration, the
compiler will assume that it returns int, and that it expects
arguments of the promoted types of the arguments you actually gave it.
If the generated code happens to work with the the actual function,
you can get what appear to be correct results. If not, arbitrarily
bad things can happen.
C99 dropped implicit int, so an attempt to call qsort with no visible
declaration would result in a mandatory diagnostic. But there are few
conforming C99 compilers yet.
But most compilers will warn you about such a call with the right
options. I advise you to find out what those options are for your
compiler, and get into the habit of using them.
Another possibility is that you might have included some other file
that directly or indirectly included <stdlib.h>. That would work, but
IMHO it's better style to have an explicit #include <stdlib.hin the
file that contains the qsort call.
--
Keith Thompson (The_Other_Keit h) ks***@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
could you be a bit less heavy handed with your snips?
Try to leave enough context in so your post can be understood
standalone.
On 9 Sep, 21:00, Ron Ford <r...@example.i nvalidwrote:
On Tue, 9 Sep 2008 01:28:09 -0700 (PDT), Nick Keighley posted:
On 9 Sep, 06:30, Ron Ford <r...@example.i nvalidwrote:
K&R has three different versions of qsort, and the ultimate one is supposed
to be like the one in the std library.
note the calling interafec may be similar but the guts don't
have to be. qsort() does not have to implement Quick Sort.
I think there's two issues here. *An implementation could modify the call
to qsort. *Chris Torek says this about that:
%- That said, I do not know of any C implementations that modify calls
%- to qsort(). *Of course, this does not guarantee that none exist.
%- (Among other things, to cross comp.lang.c threads a bit, I have
%- never seen or used a [full] C99 implementation. *Perhaps one of
%- those -- several are rumored to exist -- might substitute some
%- qsort() calls, for instance.
I don't understand what "modify calls to qsort()" means.
<snip>
*I'm trying to implement the first, which is in §4.10.
I don't understand "trying to implement". Why not copy the code
provided.
snip
that looks identical to K&R (except you stripped the comments)
I'll be the first to own up to speaking elliptically on occasion. *I don't
see it there.
again, we don't seem to be speaking the same version of english.
You don't see what where? By "implement" you mean cut-and-paste?
go and reread about arrays. eg K&R page 29
I leafed through pp25-100 and didn't see it.
p29 of my k&R has a function called getline() which takes a char[]
argument. Just above that is main() which calls getline() on line 16.
This call uses the correct syntax.
If I count correctly, this is the qsort call. *I'm not surprised that gcc
objects, as I'm not sure about this syntax at all.
good. because it's wrong
No, it was the brackets on m in the qsort call that was the culprit on line
42.
Note the bit I commented on was "If I count correctly, this is the
qsort call."
So I told you the quicksort call was wrong, so where does the "No"
above come from?
--
NIck Keighley
"You fell victim to one of the classic blunders.
The most famous is 'Never get involved in a land war in Asia,' " This thread has been closed and replies have been disabled. Please start a new discussion. |
