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

[Joachim Schmitz]

Ron Ford wrote:

On Sat, 13 Sep 2008 15:18:32 +0200, Joachim Schmitz posted:

>Ron Ford wrote:

>>On Thu, 11 Sep 2008 20:59:42 -0700, Barry Schwarz posted:

On Thu, 11 Sep 2008 21:02:19 -0600, Ron Ford <ro*@example.in valid>
wrote:
You are comparing the pointers, not the values they point to.

This seems right and behaves:

int mycmp(const void *a, const void *b)
{
int compare = 0;

if (*(const int *)a < *(const int *)b) compare = 1;
if (*(const int *)a *(const int *)b) compare = -1;
return (compare);
}

I believe the standard idiom uses some extra variables:
int mycmp(const void *a, const void *b)
{
const int *p1=a, *p2=b;
int compare = 0;

if (*p1 < *p2) compare = 1;
if (*p1 *p2) compare = -1;
return compare;
}

Saves you all these nasty casts. It's less typing too.

Bye, Jojo

Thanks, jojo, yours is a cleaner and "better" version. I adapted it
to a charsort:
int mycmp(const void *a, const void *b)
{

int compare = 0;
if (*(const char *)a < *(const char *)b) compare = 1;
if (*(const char *)a *(const char *)b) compare = -1;
return (compare);
}

int mycmp2(const void *a, const void *b)
{
const char *p1=a, *p2=b;
int compare = 0;

if (*p1 < *p2) compare = -1;
if (*p1 *p2) compare = 1;
return compare;
}

Still not perfect, overflow might occur. Better:
int mycmp2(const void *a, const void *b)
{
const char *p1=a, *p2=b;

return (*p1 *p2) - (*p1 < *p2);
}

Or with the casts:

int mycmp2(const void *a, const void *b)
{
return (*(const char *)a *(const char *)b) - (*(const char *)a < *(const
char *)b);
}

but I like the former better.

Bye, Jojo

[Ben Bacarisse]

"Joachim Schmitz" <no*********@sc hmitz-digital.dewrite s:

Ron Ford wrote:

>On Sat, 13 Sep 2008 15:18:32 +0200, Joachim Schmitz posted:

<snip>

>Thanks, jojo, yours is a cleaner and "better" version. I adapted it
to a charsort:
int mycmp(const void *a, const void *b)
{

int compare = 0;
if (*(const char *)a < *(const char *)b) compare = 1;
if (*(const char *)a *(const char *)b) compare = -1;
return (compare);
}

int mycmp2(const void *a, const void *b)
{
const char *p1=a, *p2=b;
int compare = 0;

if (*p1 < *p2) compare = -1;
if (*p1 *p2) compare = 1;
return compare;
}

Still not perfect, overflow might occur. Better:
int mycmp2(const void *a, const void *b)
{
const char *p1=a, *p2=b;

return (*p1 *p2) - (*p1 < *p2);
}

Help! How is one less prone to overflow than the other?

--
Ben.

[Richard]

Ben Bacarisse <be********@bsb .me.ukwrites:

"Joachim Schmitz" <no*********@sc hmitz-digital.dewrite s:

>Ron Ford wrote:

>>On Sat, 13 Sep 2008 15:18:32 +0200, Joachim Schmitz posted:

<snip>

>>Thanks, jojo, yours is a cleaner and "better" version. I adapted it
to a charsort:
int mycmp(const void *a, const void *b)
{

int compare = 0;
if (*(const char *)a < *(const char *)b) compare = 1;
if (*(const char *)a *(const char *)b) compare = -1;
return (compare);
}

int mycmp2(const void *a, const void *b)
{
const char *p1=a, *p2=b;
int compare = 0;

if (*p1 < *p2) compare = -1;
if (*p1 *p2) compare = 1;
return compare;
}

Still not perfect, overflow might occur. Better:
int mycmp2(const void *a, const void *b)
{
const char *p1=a, *p2=b;

return (*p1 *p2) - (*p1 < *p2);
}

Help! How is one less prone to overflow than the other?

I have never been so confused in c.l.c as this thread.

[Joachim Schmitz]

Ben Bacarisse wrote:

"Joachim Schmitz" <no*********@sc hmitz-digital.dewrite s:

>Ron Ford wrote:

>>On Sat, 13 Sep 2008 15:18:32 +0200, Joachim Schmitz posted:

<snip>

>>Thanks, jojo, yours is a cleaner and "better" version. I adapted it
to a charsort:
int mycmp(const void *a, const void *b)
{

int compare = 0;
if (*(const char *)a < *(const char *)b) compare = 1;
if (*(const char *)a *(const char *)b) compare = -1;
return (compare);
}

int mycmp2(const void *a, const void *b)
{
const char *p1=a, *p2=b;
int compare = 0;

if (*p1 < *p2) compare = -1;
if (*p1 *p2) compare = 1;
return compare;
}

Still not perfect, overflow might occur. Better:
int mycmp2(const void *a, const void *b)
{
const char *p1=a, *p2=b;

return (*p1 *p2) - (*p1 < *p2);
}

Help! How is one less prone to overflow than the other?

Sorry for the nonsens I wrote ... I meant that using

return *p1 - *p2;

as Richard at one point recommended, might overflow.

However, I'd still prefer

int mycmp2(const void *a, const void *b)
{
const char *p1=a, *p2=b;

return (*p1 *p2) - (*p1 < *p2);
}

over

int mycmp2(const void *a, const void *b)
{
const char *p1=a, *p2=b;
int compare = 0;

if (*p1 < *p2) compare = -1;
if (*p1 *p2) compare = 1;
return compare;
}
Bye, Jojo

[Joachim Schmitz]

Richard wrote:

Ben Bacarisse <be********@bsb .me.ukwrites:

>"Joachim Schmitz" <no*********@sc hmitz-digital.dewrite s:

>>Ron Ford wrote:
On Sat, 13 Sep 2008 15:18:32 +0200, Joachim Schmitz posted:

<snip>

>>>Thanks, jojo, yours is a cleaner and "better" version. I adapted
it to a charsort:
int mycmp(const void *a, const void *b)
{

int compare = 0;
if (*(const char *)a < *(const char *)b) compare = 1;
if (*(const char *)a *(const char *)b) compare = -1;
return (compare);
}

int mycmp2(const void *a, const void *b)
{
const char *p1=a, *p2=b;
int compare = 0;

if (*p1 < *p2) compare = -1;
if (*p1 *p2) compare = 1;
return compare;
}

Still not perfect, overflow might occur. Better:
int mycmp2(const void *a, const void *b)
{
const char *p1=a, *p2=b;

return (*p1 *p2) - (*p1 < *p2);
}

Help! How is one less prone to overflow than the other?

I have never been so confused in c.l.c as this thread.

Sorry about that, my fault. See my other post.

[Ralf Damaschke]

<no name givenwrote:

On Sep 13, 4:49 pm, Ralf Damaschke <[e-mail] rote:

>Richard wrote:

Richard<rgr...@ gmail.comwrites :
int mycmp(const void *a, const void *b)
{
return (*(int *)p2)-(*(int *)p1);
}

other than the obvious typo of the variable names course ...

It is not really advantageous when the result may be "either
implementati on-defined or an implementation-defined signal is
raised" (6.3.1.3).

6.3.1.3 refers to (int)LONG_MAX for example. (where LONG_MAX >
INT_MAX)
Computing (*(int *)p2)-(*(int *)p1) can result in integer overflow
which invokes undefined behavior.
Another (more clear) example is INT_MAX + 1. Just evaluating such
expression invokes undefined behavior.

Hmm, seems my search was too cursory. After doing a longer search
now I only find 6.2.5p9 which somewhat astonishes me as the
fundamental difference between signed and unsigned is introduced
in a mere subordinate clause (in a linguistic sense).

-- Ralf

[Richard]

"Joachim Schmitz" <no*********@sc hmitz-digital.dewrite s:

Ben Bacarisse wrote:

>"Joachim Schmitz" <no*********@sc hmitz-digital.dewrite s:

>>Ron Ford wrote:
On Sat, 13 Sep 2008 15:18:32 +0200, Joachim Schmitz posted:

<snip>

>>>Thanks, jojo, yours is a cleaner and "better" version. I adapted it
to a charsort:
int mycmp(const void *a, const void *b)
{

int compare = 0;
if (*(const char *)a < *(const char *)b) compare = 1;
if (*(const char *)a *(const char *)b) compare = -1;
return (compare);
}

int mycmp2(const void *a, const void *b)
{
const char *p1=a, *p2=b;
int compare = 0;

if (*p1 < *p2) compare = -1;
if (*p1 *p2) compare = 1;
return compare;
}

Still not perfect, overflow might occur. Better:
int mycmp2(const void *a, const void *b)
{
const char *p1=a, *p2=b;

return (*p1 *p2) - (*p1 < *p2);
}

Help! How is one less prone to overflow than the other?

Sorry for the nonsens I wrote ... I meant that using

return *p1 - *p2;

as Richard at one point recommended, might overflow.

It might. But since its a "home rolled" function tend to know the
numbers range. So perfect, and fast, when the ints do not reach ranges
where overflow might occur ....

I wonder what your code looks like where other subtractions with ints
are done. Do you compare them all the time before hand?

[vippstar]

On Sep 14, 6:56 pm, Ralf Damaschke <[e-mail] rote:

<no name givenwrote:

On Sep 13, 4:49 pm, Ralf Damaschke <[e-mail] rote:

Richard wrote:
Richard<rgr...@ gmail.comwrites :
int mycmp(const void *a, const void *b)
{
return (*(int *)p2)-(*(int *)p1);
}

other than the obvious typo of the variable names course ...

It is not really advantageous when the result may be "either
implementation-defined or an implementation-defined signal is
raised" (6.3.1.3).

6.3.1.3 refers to (int)LONG_MAX for example. (where LONG_MAX >
INT_MAX)
Computing (*(int *)p2)-(*(int *)p1) can result in integer overflow
which invokes undefined behavior.
Another (more clear) example is INT_MAX + 1. Just evaluating such
expression invokes undefined behavior.

Hmm, seems my search was too cursory. After doing a longer search
now I only find 6.2.5p9 which somewhat astonishes me as the
fundamental difference between signed and unsigned is introduced
in a mere subordinate clause (in a linguistic sense).

I'm curious, why "<no name given>"?

[Keith Thompson]

vi******@gmail. com writes:

On Sep 14, 6:56 pm, Ralf Damaschke <[e-mail] rote:

><no name givenwrote:

[25 lines deleted]

>
I'm curious, why "<no name given>"?

Was it necessary to quote the entire article to ask that question?

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

[vippstar]

On Sep 14, 9:00 pm, Keith Thompson <[e-mail] rote:

vipps...@gmail. com writes:

On Sep 14, 6:56 pm, Ralf Damaschke <[e-mail] rote:

<no name givenwrote:

[25 lines deleted]

I'm curious, why "<no name given>"?

Was it necessary to quote the entire article to ask that question?

No... I admit I'm not a good snipper.