Velocity Reviews > calling qsort

calling qsort

Ron Ford
Guest
Posts: n/a

 09-09-2008
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\source>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

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

s.dhilipkumar@gmail.com
Guest
Posts: n/a

 09-09-2008
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

Nick Keighley
Guest
Posts: n/a

 09-09-2008
On 9 Sep, 06:30, Ron Ford <(E-Mail Removed)> wrote:

> 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);

>
> * for (i=0; i < size; ++ i) *printf(" %d \n ", m[i]);
>
> * return 0;
>
> }
>
> // gcc -o sort c5.c
>
> gcc objects with:
>
> F:\gfortran\source>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

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

Nate Eldredge
Guest
Posts: n/a

 09-09-2008
Ron Ford <(E-Mail Removed)> writes:

> 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:
>

[snip definitions of `qsort', `swap', which look okay]
>
> #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\source>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

Right. You just want to say

qsort(m, 0, size - 1);

When you use the name of an array without subscripting, it turns into
a pointer to its first element, same as if you wrote &(m[0]). This is
what gets passed to qsort, which is allowed to interpret it as an
array.

This is a pretty fundamental concept in C, so I'd recommend carefully
reading the relevant section in K&R. (Don't have it handy to look up
the chapter number.)

> 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 *)

The fourth argument is a pointer to a function which handles your
comparison. If you want to sort your array of ints, you would do:

int mycmp(const void *a, const void *b) {
return (*(const int *)a < *(const int *)b);
}

void other_func(void) {
int m[size];
....
qsort(m, size, sizeof(int), mycmp);
}

Further study may be needed in order to fully comprehend this,
depending on how comfortable you are with function pointers, pointer
casts, and sizeof.

Ron Ford
Guest
Posts: n/a

 09-09-2008
On Tue, 9 Sep 2008 01:14:50 -0700 (PDT), http://www.velocityreviews.com/forums/(E-Mail Removed) 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\source>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

Ron Ford
Guest
Posts: n/a

 09-09-2008
On Tue, 9 Sep 2008 01:28:09 -0700 (PDT), Nick Keighley posted:

> On 9 Sep, 06:30, Ron Ford <(E-Mail Removed)> wrote:
>
>> 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.f95 on Wed Aug 27 17:16:03 2008
MD5:2948eeeeb93405ec66df04faa2275dfe -- 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_module' 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.

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

>
> 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
Guest
Posts: n/a

 09-09-2008
On Tue, 09 Sep 2008 08:05:24 -0700, Nate Eldredge posted:

>> 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 *)

>
> The fourth argument is a pointer to a function which handles your
> comparison. If you want to sort your array of ints, you would do:
>
> int mycmp(const void *a, const void *b) {
> return (*(const int *)a < *(const int *)b);
> }
>
> void other_func(void) {
> int m[size];
> ....
> qsort(m, size, sizeof(int), mycmp);
> }
>
> Further study may be needed in order to fully comprehend this,
> depending on how comfortable you are with function pointers, pointer
> casts, and sizeof.

Thanks for your help, Nate. I think I got the upper hand on it now. Your
comparison function is written to sort in descending order, so I let it
unsort what the K&R sort did:

void qsort1(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);
qsort1(v, left, last - 1);
qsort1(v, last + 1, right);

}

void swap(int v[], int i, int j)
{
int temp;

temp = v[i];
v[i] = v[j];
v[j] = temp;
}

int mycmp(const void *a, const void *b) {
return (*(const int *)a < *(const int *)b);
}

#include <stdio.h>
#define size 9

int main(void)
{
int m[size], i;

for (i=0; i < size; ++ i)
{
m[i] = size - i;
printf(" %d \n ", m[i]);
}

qsort1 (m, 0, size - 1);
for (i=0; i < size; ++ i) printf(" %d \n ", m[i]);

// call library qsort
qsort(m, size, sizeof(int), mycmp);
for (i=0; i < size; ++ i) printf(" %d \n ", m[i]);

return 0;
}

// gcc -o sort c6.c

F:\gfortran\source>gcc -o sort c6.c

F:\gfortran\source>sort
9
8
7
6
5
4
3
2
1
1
2
3
4
5
6
7
8
9
9
8
7
6
5
4
3
2
1

The problem with getting this right is that I have no excuse now to avoid
the day's work.
--
Wealth - any income that is at least one hundred dollars more a year than
the income of one's wife's sister's husband. 6
H. L. Mencken

Flash Gordon
Guest
Posts: n/a

 09-09-2008
Malcolm McLean wrote, On 09/09/08 21:38:
>
> "Ron Ford" <(E-Mail Removed)> wrote 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

> That's typical. Bread and butter code is written portably and with an
> emphasis on readability and maintainablility (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

Ron Ford
Guest
Posts: n/a

 09-09-2008
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.

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

Keith Thompson
Guest
Posts: n/a

 09-10-2008
Ron Ford <(E-Mail Removed)> writes:
[...]
> The part I don't get right now is why the call to qsort worked without
> #include <stdlib.h>
>
> ?

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

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.h> in the
file that contains the qsort call.

--
Keith Thompson (The_Other_Keith) (E-Mail Removed) <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"

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post Charlie Zender C Programming 21 01-03-2004 12:32 PM Ingo Brueckl C Programming 5 12-19-2003 01:08 AM Debashish Chakravarty C Programming 0 11-23-2003 04:59 AM richard C Programming 34 08-28-2003 12:10 PM richard C Programming 0 08-13-2003 11:09 PM