calling qsort

[Ron Ford]

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

)
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;
v = 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 - size;
printf(" %d \n ", m);
}

qsort (m[], 0, size - 1);

for (i=0; i < size; ++ i) printf(" %d \n ", m);

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
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,​

 

[s.dhilipkumar]

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 = size - i;
---

m = i - size;

43c43
< qsort (m, 0, size - 1);
---

qsort (m[], 0, size - 1);

Regards,
Dhilip

 

[Nick Keighley]

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

)
      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;
  v = 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 - size;
        printf(" %d \n ", m);
    }

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

  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
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.​

 

[Nate Eldredge]

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 - size;
printf(" %d \n ", m);
}

qsort (m[], 0, size - 1);

for (i=0; i < size; ++ i) printf(" %d \n ", m);

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
objects, as I'm not sure about this syntax at all.

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]

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 = size - i;
---

m = 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

 

[Ron Ford]

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

good. because it's wrong

No, it was the brackets on m in the qsort call that was the culprit on line
42.

 

[Ron Ford]

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

)
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;
v = 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 = size - i;
printf(" %d \n ", m);
}

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



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

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.:-(​

 

[Flash Gordon]

Malcolm McLean wrote, On 09/09/08 21:38:
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 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.

 

[Ron Ford]

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>

?

 

[Keith Thompson]

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

 

[Nick Keighley]

could you be a bit less heavy handed with your snips?
Try to leave enough context in so your post can be understood
standalone.

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.

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?

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.

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?

 

[Ron Ford]

could you be a bit less heavy handed with your snips?
Try to leave enough context in so your post can be understood
standalone.

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.

I'm appropriately uncomfortable trying to elaborate on what Chris, in a
slightly differing context, writes. I think the idea is that if you printf
the word "hi," your implementation could instead putchar h and i.

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?

If you cut and paste with a book, you destroy its future value.
"Implement" means making the necessary keystrokes to make code work.

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.

The calls on pg 29 are for char arrays and have brackets. My error was
that I had to lose the brackets.

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,' "

The error on line 42 no longer exists. It just occured to me that "don't
get in a land war in Asia" is precisely what the texans did.

 

[Ron Ford]

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

Thanks, Keith. I thought I'd crank up the warnings and don't know what I'm
seeing.


F:\gfortran\source>gcc -o sort -Wall -pedantic -ansi c6.c
c6.c: In function 'main':
c6.c:51: error: expected expression before '/' token
c6.c: At top level:
c6.c:58: error: expected identifier or '(' before '/' token

Lines 51 and 58 are comments. Just to see if they would work otherwise, I
compiled with no flags and was successful:

F:\gfortran\source>gcc c6.c

issues no diagnostics. I thought it might be to lack of inclusion of
stdlib.h, but I get the same thing after I add it:

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

)
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;
v = v[j];
v[j] = temp;
}

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

#include <stdio.h>
#include <stdlib.h>
#define size 9

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

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

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



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

return 0;
}

// gcc -o sort -Wall -pedantic -ansi c6.c line 58


F:\gfortran\source>gcc -o sort -Wall -pedantic -ansi c6.c
c6.c: In function 'main':
c6.c:52: error: expected expression before '/' token
c6.c: At top level:
c6.c:59: error: expected identifier or '(' before '/' token

Is '//' not a kosher comment?​

 

[vippstar]

Is '//' not a kosher comment?

No Ron, // is not a "kosher comment".
Where have you heard that? What is this nonsensical babbling that
frequently appears in your posts?
More importantly, why are some still bothering with you?

 

[Keith Thompson]

Is '//' not a kosher comment?

It's a valid comment in C99. It's not a valid comment in C90. The
"-ansi" option (along with "-pedantic" causes gcc to conform to C90.

(You've been hanging out in this group for a while; I'm surprised you
didn't know that.)

 

[Richard]

No Ron, // is not a "kosher comment".
Where have you heard that? What is this nonsensical babbling that
frequently appears in your posts?
More importantly, why are some still bothering with you?

What on earth are you babbling about? // is a perfectly good comment
prefix.

 

[Ron Ford]

No Ron, // is not a "kosher comment".
Where have you heard that? What is this nonsensical babbling that
frequently appears in your posts?
More importantly, why are some still bothering with you?

[comp.lang.c]
!delete From {vippstar}

 

[Ron Ford]

It's a valid comment in C99. It's not a valid comment in C90. The
"-ansi" option (along with "-pedantic" causes gcc to conform to C90.

(You've been hanging out in this group for a while; I'm surprised you
didn't know that.)

I'm promiscuous with syntax and compilers. Comments are the last thing I
remember; they're almost like comments. Is /* ...*/ the only legal C90
comment?

 

[vippstar]

[...]

Is '//' not a kosher comment?

It's a valid comment in C99. It's not a valid comment in C90. The
"-ansi" option (along with "-pedantic" causes gcc to conform to C90.

(You've been hanging out in this group for a while; I'm surprised you
didn't know that.)

For a while?! Here's a quote from Ron Ford:

These made great reading. It's been years since I've read Dan Pop.

Years. He reads Dan Pop, the standard too. (see the message) Yet, //
is a "kosher comment".

Here, in this article, <[email protected]>, he
correctly uses the // comment, and compiles with -std=c99.
Why did he choose to change it to -ansi -pedantic, while using //?
Wouldn't he remember that with -std=c99 it worked? Isn't that a hint
that it's a C99 feature?

Here's another article of his, <[email protected]>.
In this one, he seems quite confident to claim that // is indeed a
comment.
(He also suggests to look at the 7th chapter of K&R, though //
comments are not mentioned at all in K&R...)
Plus, the usual nonsense.

Keith, why do you still bother? It's your right to do so, if you want,
but it puzzles me.

 

[Ron Ford]

What on earth are you babbling about? // is a perfectly good comment
prefix.

I did a little reading for flags in gcc.pdf, and I think this is what I
wanted for when I didn't have stdlib included:

F:\gfortran\source>gcc -o sort -Wall c6.c
c6.c: In function 'main':
c6.c:53: warning: implicit declaration of function 'qsort'


I looked in stdlib.h and found the declaration for qsort for my
implementation.

_CRTIMP void __cdecl qsort(void*, size_t, size_t,
int (*)(const void*, const void*));

Does this suggest a better search for google to find the source for my
qsort implementation than "qsort.c gcc source?"