Is there any way to refer to another array in qsort's compare function?

[Stone]

Here's the problem.

I wrote a function 'int my_compare(const void *, const void *);' and
passed it to qsort() of stdlib.h, in order to sort an array named
*ptr* which contains indices of another array *data*. By that I
intended to sort elements of *ptr* (i.e. ptr) using data[ptr] as
the key value.

However, the *data* array was defined as static in main(), and seemed
not easy to access in my_compare(). Is there any way to achieve this?

Thanks&Regards.

Stone.

 

[Dr Nick]

Here's the problem.

I wrote a function 'int my_compare(const void *, const void *);' and
passed it to qsort() of stdlib.h, in order to sort an array named
*ptr* which contains indices of another array *data*. By that I
intended to sort elements of *ptr* (i.e. ptr) using data[ptr] as
the key value.

However, the *data* array was defined as static in main(), and seemed
not easy to access in my_compare(). Is there any way to achieve this?

Not that I know of. It's a design flaw in the standard library IMO -
any function that takes a user provided function and calls it in this
way should take an extra, void *, parameter that it passes to the called
function. After all, it can always be NULL. In this case, it could
carry a pointer to your "data" array.

There are non-standard versions of qsort (usually called qsort_r or
qsort_s) that do this, but whether you have access to one, and how
concerned you are about portability will feature in your decision on
whether to this or whether to make your array global (or to have a
global pointer to it - suitably named and identified).

Anyone know if this is going to appear in standard C (and if not, why
not?; it seems a clear flaw to me).

 

[Ben Bacarisse]

Here's the problem.

I wrote a function 'int my_compare(const void *, const void *);' and
passed it to qsort() of stdlib.h, in order to sort an array named
*ptr* which contains indices of another array *data*. By that I
intended to sort elements of *ptr* (i.e. ptr) using data[ptr] as
the key value.

However, the *data* array was defined as static in main(), and seemed
not easy to access in my_compare(). Is there any way to achieve this?

You can either move the array so that it is defined at file scope
(i.e. outside main) or you can arrange for there to be a file-scope
pointer to it:

#include <stdlib.h>
#include <stdio.h>

int *aux_sort_ptr;

int my_compare(const void *p1, const void *p2)
{
const int *ip1 = p1, *ip2 = p2;
return aux_sort_ptr[*ip1] - aux_sort_ptr[*ip2];
}

int main(void)
{
static int data[] = { 3, 1, 2 };
int idx[] = { 1, 2, 3 };
aux_sort_ptr = data;
qsort(idx, sizeof idx/sizeof *idx, sizeof *idx, my_compare);
for (int i = 0; i < sizeof idx/sizeof *idx; i++)
printf("idx[%d] = %d, data[%d] = %d\n",
i, idx, idx, data[idx]);
}

This is ugly (and problematic in threaded code), but there's no elegant
way round it using standard C. Many systems have other sort functions
whose comparison function can be handed another void * (see Dr Nick's
reply) but I don't think and have become common enough to though of as
"almost standard".

 

[88888 Dihedral]

Ben Bacarisseæ–¼ 2011å¹´12月29日星期四UTC+8下åˆ7時58分14秒寫é“：

Here's the problem.

I wrote a function 'int my_compare(const void *, const void *);' and
passed it to qsort() of stdlib.h, in order to sort an array named
*ptr* which contains indices of another array *data*. By that I
intended to sort elements of *ptr* (i.e. ptr) using data[ptr] as
the key value.

However, the *data* array was defined as static in main(), and seemed
not easy to access in my_compare(). Is there any way to achieve this?

You can either move the array so that it is defined at file scope
(i.e. outside main) or you can arrange for there to be a file-scope
pointer to it:

#include <stdlib.h>
#include <stdio.h>

int *aux_sort_ptr;

int my_compare(const void *p1, const void *p2)
{
const int *ip1 = p1, *ip2 = p2;
return aux_sort_ptr[*ip1] - aux_sort_ptr[*ip2];
}

int main(void)
{
static int data[] = { 3, 1, 2 };
int idx[] = { 1, 2, 3 };
aux_sort_ptr = data;
qsort(idx, sizeof idx/sizeof *idx, sizeof *idx, my_compare);
for (int i = 0; i < sizeof idx/sizeof *idx; i++)
printf("idx[%d] = %d, data[%d] = %d\n",
i, idx, idx, data[idx]);
}

This is ugly (and problematic in threaded code), but there's no elegant
way round it using standard C. Many systems have other sort functions
whose comparison function can be handed another void * (see Dr Nick's
reply) but I don't think and have become common enough to though of as
"almost standard".

This method uses more memory. Do you think that just
overloading the comparison function by OOP can make it not choking at all?

 

[Dr Nick]

Ben Bacarisseæ–¼ 2011å¹´12月29日星期四UTC+8下åˆ7時58分14秒寫é“：

Here's the problem.

I wrote a function 'int my_compare(const void *, const void *);' and
passed it to qsort() of stdlib.h, in order to sort an array named
*ptr* which contains indices of another array *data*. By that I
intended to sort elements of *ptr* (i.e. ptr) using data[ptr] as
the key value.

However, the *data* array was defined as static in main(), and seemed
not easy to access in my_compare(). Is there any way to achieve this?

You can either move the array so that it is defined at file scope
(i.e. outside main) or you can arrange for there to be a file-scope
pointer to it:

#include <stdlib.h>
#include <stdio.h>

int *aux_sort_ptr;

int my_compare(const void *p1, const void *p2)
{
const int *ip1 = p1, *ip2 = p2;
return aux_sort_ptr[*ip1] - aux_sort_ptr[*ip2];
}

int main(void)
{
static int data[] = { 3, 1, 2 };
int idx[] = { 1, 2, 3 };
aux_sort_ptr = data;
qsort(idx, sizeof idx/sizeof *idx, sizeof *idx, my_compare);
for (int i = 0; i < sizeof idx/sizeof *idx; i++)
printf("idx[%d] = %d, data[%d] = %d\n",
i, idx, idx, data[idx]);
}

This is ugly (and problematic in threaded code), but there's no elegant
way round it using standard C. Many systems have other sort functions
whose comparison function can be handed another void * (see Dr Nick's
reply) but I don't think and have become common enough to though of as
"almost standard".

This method uses more memory.

One pointer's worth.

Do you think that just
overloading the comparison function by OOP can make it not choking at all?

Why do you say that "Do you think that just overloading the comparison
function by OOP can make it not choking at all?"

To Stone: No-one has a clue what 88888 Dihedral is on about. Many of us
suspect him to be a poor attempt to pass the Turing test. Whatever he
is, don't worry about his comments.

 

[88888 Dihedral]

Dr Nickæ–¼ 2011å¹´12月29日星期四UTC+8下åˆ8時37分26秒寫é“：

Ben Bacarisseæ–¼ 2011å¹´12月29日星期四UTC+8下åˆ7時58分14秒寫é“：

Here's the problem.

I wrote a function 'int my_compare(const void *, const void *);' and
passed it to qsort() of stdlib.h, in order to sort an array named
*ptr* which contains indices of another array *data*. By that I
intended to sort elements of *ptr* (i.e. ptr) using data[ptr] as
the key value.

However, the *data* array was defined as static in main(), and seemed
not easy to access in my_compare(). Is there any way to achieve this?

You can either move the array so that it is defined at file scope
(i.e. outside main) or you can arrange for there to be a file-scope
pointer to it:

#include <stdlib.h>
#include <stdio.h>

int *aux_sort_ptr;

int my_compare(const void *p1, const void *p2)
{
const int *ip1 = p1, *ip2 = p2;
return aux_sort_ptr[*ip1] - aux_sort_ptr[*ip2];
}

int main(void)
{
static int data[] = { 3, 1, 2 };
int idx[] = { 1, 2, 3 };
aux_sort_ptr = data;
qsort(idx, sizeof idx/sizeof *idx, sizeof *idx, my_compare);
for (int i = 0; i < sizeof idx/sizeof *idx; i++)
printf("idx[%d] = %d, data[%d] = %d\n",
i, idx, idx, data[idx]);
}

This is ugly (and problematic in threaded code), but there's no elegant
way round it using standard C. Many systems have other sort functions
whose comparison function can be handed another void * (see Dr Nick's
reply) but I don't think and have become common enough to though of as
"almost standard".

This method uses more memory.

One pointer's worth.

Do you think that just
overloading the comparison function by OOP can make it not choking at all?

Why do you say that "Do you think that just overloading the comparison
function by OOP can make it not choking at all?"

To Stone: No-one has a clue what 88888 Dihedral is on about. Many of us
suspect him to be a poor attempt to pass the Turing test. Whatever he
is, don't worry about his comments.

Just feed a segment of repeated integers, say, 3,4,5,6,3,4, 5, 6
3,4,5, 6.... for several thousands then the program you posted will choke at the segment.

 

[Dr Nick]

Dr Nickæ–¼ 2011å¹´12月29日星期四UTC+8下åˆ8時37分26秒寫é“：

Ben Bacarisseæ–¼ 2011å¹´12月29日星期四UTC+8下åˆ7時58分14秒寫é“：

Here's the problem.

I wrote a function 'int my_compare(const void *, const void *);' and
passed it to qsort() of stdlib.h, in order to sort an array named
*ptr* which contains indices of another array *data*. By that I
intended to sort elements of *ptr* (i.e. ptr) using data[ptr] as
the key value.

However, the *data* array was defined as static in main(), and seemed
not easy to access in my_compare(). Is there any way to achieve this?

You can either move the array so that it is defined at file scope
(i.e. outside main) or you can arrange for there to be a file-scope
pointer to it:

#include <stdlib.h>
#include <stdio.h>

int *aux_sort_ptr;

int my_compare(const void *p1, const void *p2)
{
const int *ip1 = p1, *ip2 = p2;
return aux_sort_ptr[*ip1] - aux_sort_ptr[*ip2];
}

int main(void)
{
static int data[] = { 3, 1, 2 };
int idx[] = { 1, 2, 3 };
aux_sort_ptr = data;
qsort(idx, sizeof idx/sizeof *idx, sizeof *idx, my_compare);
for (int i = 0; i < sizeof idx/sizeof *idx; i++)
printf("idx[%d] = %d, data[%d] = %d\n",
i, idx, idx, data[idx]);
}

This is ugly (and problematic in threaded code), but there's no elegant
way round it using standard C. Many systems have other sort functions
whose comparison function can be handed another void * (see Dr Nick's
reply) but I don't think and have become common enough to though of as
"almost standard".

This method uses more memory.

One pointer's worth.

Do you think that just
overloading the comparison function by OOP can make it not choking at all?

Why do you say that "Do you think that just overloading the comparison
function by OOP can make it not choking at all?"

To Stone: No-one has a clue what 88888 Dihedral is on about. Many of us
suspect him to be a poor attempt to pass the Turing test. Whatever he
is, don't worry about his comments.

Just feed a segment of repeated integers, say, 3,4,5,6,3,4, 5, 6
3,4,5, 6.... for several thousands then the program you posted will choke at the segment.

See what I mean? It's complete gibberish without any context,
understanding of code or relevance to the question.

a) I didn't post any program
b) The only way this differs from what the OP described but didn't post
is that aux_pointer has been added.
c) Changing the comparison function will have no effect on the memory
used
d) Do you ever answer questions or just spray out this stuff?

Sorry to the rest of you for this, I'm not yet killfiling him as I worry
that he'll confuse people asking for help. I'm also trying to diagnose
what's going on.

 

[Ben Bacarisse]

Here's the problem.

I wrote a function 'int my_compare(const void *, const void *);' and
passed it to qsort() of stdlib.h, in order to sort an array named
*ptr* which contains indices of another array *data*. By that I
intended to sort elements of *ptr* (i.e. ptr) using data[ptr] as
the key value.

However, the *data* array was defined as static in main(), and seemed
not easy to access in my_compare(). Is there any way to achieve this?

MacOSX has qsort_r which passes a context pointer to qsort_r which, in turn,
passes it to the compare. I don't know if other implementations have this.

It's in most modern versions of the GNU C library (apparently since
version 2.8) but it's not documented yet. I think qsort_r is probably
close to being reliably available on *nix type systems but I don't know
about Windows C libraries.

For the record, here's the same program I posted but using qsort_r:

#include <stdlib.h>
#include <stdio.h>

int my_compare(const void *p1, const void *p2, void *cp)
{
const int *ip1 = p1, *ip2 = p2, *aux_sort_ptr = cp;
return aux_sort_ptr[*ip1] - aux_sort_ptr[*ip2];
}

int main(void)
{
static int data[] = { 3, 1, 2 };
int idx[] = { 1, 2, 3 };
qsort_r(idx, sizeof idx/sizeof *idx, sizeof *idx, my_compare, data);
for (int i = 0; i < sizeof idx/sizeof *idx; i++)
printf("idx[%d] = %d, data[%d] = %d\n",
i, idx, idx, data[idx]);
}

(compile, on modern Linux at least, with -std=c99 -D_GNU_SOURCE)

 

[Ben Bacarisse]

Bull in a China Blue Shop <[email protected]> writes:

It's in most modern versions of the GNU C library (apparently since
version 2.8) but it's not documented yet.

Argh! I decided to write the missing man page and in so doing I found
the following mess:

The GNU version has prototype

void qsort_r(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *, void *),
void *data);

I.e. the data pointer is last and gets passed as the third argument to
the comparison function.

The BSD version is

void qsort_r(void *base, size_t nmemb, size_t size, void *data,
int (*compar)(void *, const void *, const void *));

with the data pointer as the fourth argument which gets passed as the
first argument to the comparison function.

Microsoft decided to do this:

void qsort_s(void *base, size_t nmemb, size_t size,
int (*compare)(void *, const void *, const void *),
void *data);

using the argument order of the GNU version and the comparison function
of the BSD version.

Annex K of the new C standard defines an option set of library extension
based on Microsoft's supposedly "safer" functions. Here we find (edited
for consistency):

errno_t qsort_s(void *base, rsize_t nmemb, rsize_t size,
int (*compar)(const void *, const void *, void *),
void *data);

which follows the GNU version except for the name and the return type!
I don't know why the online documentation for Microsoft systems does not
used this version.

I think qsort_r is probably
close to being reliably available on *nix type systems but I don't know
about Windows C libraries.

So, no. There is no widely available qsort function that takes a data
pointer. If the documentation is right, you can't even use the
quasi-standard qsort_s with Microsoft's C library.

It's a shame that we are left with this mess. Annex K is optional, and
is an all-or-nothing set of extensions (I may have misunderstood that)
so qsort_s is likely to languish alongside all the other _s functions.
qsort_r is functionally better that qsort -- the change is not a
mythical safety advantage.

<snip>

 

[James Kuyper]

Here's the problem.

I wrote a function 'int my_compare(const void *, const void *);' and
passed it to qsort() of stdlib.h, in order to sort an array named
*ptr* which contains indices of another array *data*. By that I
intended to sort elements of *ptr* (i.e. ptr) using data[ptr] as
the key value.

However, the *data* array was defined as static in main(), and seemed
not easy to access in my_compare(). Is there any way to achieve this?

One alternative is to redefine ptr to contain pointers, rather than
indices, so instead of using data[ptr] you use *ptr.

 

[88888 Dihedral]

Ben Bacarisseæ–¼ 2011å¹´12月29日星期四UTC+8下åˆ11時29分16秒寫é“：

Argh! I decided to write the missing man page and in so doing I found
the following mess:

The GNU version has prototype

void qsort_r(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *, void *),
void *data);

I.e. the data pointer is last and gets passed as the third argument to
the comparison function.

The BSD version is

void qsort_r(void *base, size_t nmemb, size_t size, void *data,
int (*compar)(void *, const void *, const void *));

with the data pointer as the fourth argument which gets passed as the
first argument to the comparison function.

Microsoft decided to do this:

void qsort_s(void *base, size_t nmemb, size_t size,
int (*compare)(void *, const void *, const void *),
void *data);

using the argument order of the GNU version and the comparison function
of the BSD version.

Annex K of the new C standard defines an option set of library extension
based on Microsoft's supposedly "safer" functions. Here we find (edited
for consistency):

errno_t qsort_s(void *base, rsize_t nmemb, rsize_t size,
int (*compar)(const void *, const void *, void *),
void *data);

which follows the GNU version except for the name and the return type!
I don't know why the online documentation for Microsoft systems does not
used this version.


So, no. There is no widely available qsort function that takes a data
pointer. If the documentation is right, you can't even use the
quasi-standard qsort_s with Microsoft's C library.

It's a shame that we are left with this mess. Annex K is optional, and
is an all-or-nothing set of extensions (I may have misunderstood that)
so qsort_s is likely to languish alongside all the other _s functions.
qsort_r is functionally better that qsort -- the change is not a
mythical safety advantage.

<snip>

Use merge sort or heap sort or enhanced radix sort.

 

[Geoff]

Sorry to the rest of you for this, I'm not yet killfiling him as I worry
that he'll confuse people asking for help. I'm also trying to diagnose
what's going on.

His English syntax is Asian. His IP suggests Taiwan. His style is that
of a young troll with time on his hands.

 

[James Kuyper]

On 12/29/2011 07:59 AM, Dr Nick wrote:
....

Sorry to the rest of you for this, I'm not yet killfiling him as I worry
that he'll confuse people asking for help. ...

I used to feel that way about trolls - but any response encourages them,
and aggravates you; it's not clear that the newbies you're trying to
protect gain any benefit to compensate for those facts. Even a newbie
will recognize pretty quickly that this guy's "responses" are
non-responsive and meaningless. There are trolls who use subtler
techniques that are harder for a newbie to recognize, but most don't bother.

 

[88888 Dihedral]

Ben Bacarisseæ–¼ 2011å¹´12月29日星期四UTC+8下åˆ11時29分16秒寫é“：

Argh! I decided to write the missing man page and in so doing I found
the following mess:

The GNU version has prototype

void qsort_r(void *base, size_t nmemb, size_t size,
int (*compar)(const void *, const void *, void *),
void *data);

I.e. the data pointer is last and gets passed as the third argument to
the comparison function.

The BSD version is

void qsort_r(void *base, size_t nmemb, size_t size, void *data,
int (*compar)(void *, const void *, const void *));

with the data pointer as the fourth argument which gets passed as the
first argument to the comparison function.

Microsoft decided to do this:

void qsort_s(void *base, size_t nmemb, size_t size,
int (*compare)(void *, const void *, const void *),
void *data);

using the argument order of the GNU version and the comparison function
of the BSD version.

Annex K of the new C standard defines an option set of library extension
based on Microsoft's supposedly "safer" functions. Here we find (edited
for consistency):

errno_t qsort_s(void *base, rsize_t nmemb, rsize_t size,
int (*compar)(const void *, const void *, void *),
void *data);

which follows the GNU version except for the name and the return type!
I don't know why the online documentation for Microsoft systems does not
used this version.


So, no. There is no widely available qsort function that takes a data
pointer. If the documentation is right, you can't even use the
quasi-standard qsort_s with Microsoft's C library.

It's a shame that we are left with this mess. Annex K is optional, and
is an all-or-nothing set of extensions (I may have misunderstood that)
so qsort_s is likely to languish alongside all the other _s functions.
qsort_r is functionally better that qsort -- the change is not a
mythical safety advantage.

<snip>

A you joking about using the lousy quicksort in the standard lib as posted
by the top post here ?

Take a look at some real applications of sorting required in the
data compression in BWT or the DNA sequencing problem.







problem

 

[88888 Dihedral]

I think you are lousy and somewhat bigotry in this news group.

If you can't show your code and understanding of any descent language,
then do we have to clearly to say that you are not gifted to write programs
here ?

 

[88888 Dihedral]

If you can't reply to the sorting problem in C posted,
then I doubt why you are here?

Are u really capable of speaking some descent language or writing some
useful computer languages?

 

[Geoff]

I think you are lousy and somewhat bigotry in this news group.

If you can't show your code and understanding of any descent language,
then do we have to clearly to say that you are not gifted to write programs
here ?

Touched a nerve, did I? It proves you are probably not a Turing bot
then. My wife is Chinese and I have been to China and Taiwan several
times. I know I'm not bigoted but I can't say the same about your
reaction. This is all I have to say to you on this topic.

I am happy to lurk and post occasionally when I have something to say
about the language or post comments on code. I will not post because
you say so.

 

[88888 Dihedral]

Geoffæ–¼ 2011å¹´12月30日星期五UTC+8上åˆ11時29分17秒寫é“：

Touched a nerve, did I? It proves you are probably not a Turing bot
then. My wife is Chinese and I have been to China and Taiwan several
times. I know I'm not bigoted but I can't say the same about your
reaction. This is all I have to say to you on this topic.

I am happy to lurk and post occasionally when I have something to say
about the language or post comments on code. I will not post because
you say so.

Kind of boring for this old problem. Even in the case that the quick sort won't choke at all, it is still too slow in DNA sequencing problems.

 

[88888 Dihedral]

Bull in a China Blue Shopæ–¼ 2011å¹´12月30日星期五UTC+8下åˆ4時52分12秒寫é“：

Hint: most people don't give a shit whether qsort uses quicksort. On unices, at
least, you can replace it with whatever you want with ld.

--
My name Indigo Montoya. | Yippie-kay-yay, mother fakir.
You flamed my father. | I'm whoever you want me to be.
Prepare to be spanked. | Annoying Usenet one post at a time.
Stop posting that! | At least I can stay in character.

The sweet spot of the quick sort is to sort a set of 200-2000 items
if not choked when used.

Also the merge sort is better in distributed computing.

 

[88888 Dihedral]

Dr Nickæ–¼ 2011å¹´12月29日星期四UTC+8下åˆ8時37分26秒寫é“：

Ben Bacarisseæ–¼ 2011å¹´12月29日星期四UTC+8下åˆ7時58分14秒寫é“：

Here's the problem.

I wrote a function 'int my_compare(const void *, const void *);' and
passed it to qsort() of stdlib.h, in order to sort an array named
*ptr* which contains indices of another array *data*. By that I
intended to sort elements of *ptr* (i.e. ptr) using data[ptr] as
the key value.

However, the *data* array was defined as static in main(), and seemed
not easy to access in my_compare(). Is there any way to achieve this?

You can either move the array so that it is defined at file scope
(i.e. outside main) or you can arrange for there to be a file-scope
pointer to it:

#include <stdlib.h>
#include <stdio.h>

int *aux_sort_ptr;

int my_compare(const void *p1, const void *p2)
{
const int *ip1 = p1, *ip2 = p2;
return aux_sort_ptr[*ip1] - aux_sort_ptr[*ip2];
}

int main(void)
{
static int data[] = { 3, 1, 2 };
int idx[] = { 1, 2, 3 };
aux_sort_ptr = data;
qsort(idx, sizeof idx/sizeof *idx, sizeof *idx, my_compare);
for (int i = 0; i < sizeof idx/sizeof *idx; i++)
printf("idx[%d] = %d, data[%d] = %d\n",
i, idx, idx, data[idx]);
}

This is ugly (and problematic in threaded code), but there's no elegant
way round it using standard C. Many systems have other sort functions
whose comparison function can be handed another void * (see Dr Nick's
reply) but I don't think and have become common enough to though of as
"almost standard".

This method uses more memory.

One pointer's worth.

Do you think that just
overloading the comparison function by OOP can make it not choking at all?

Why do you say that "Do you think that just overloading the comparison
function by OOP can make it not choking at all?"

To Stone: No-one has a clue what 88888 Dihedral is on about. Many of us
suspect him to be a poor attempt to pass the Turing test. Whatever he
is, don't worry about his comments.

Because I wrote a non-choking quicksort myself long time ago for
a list of structures in C.

Of course my program in the final version read in tens of thousands
of records from the hard disk.