Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Is there any way to refer to another array in qsort's compare function?

Reply
Thread Tools

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

 
 
88888 Dihedral
Guest
Posts: n/a
 
      01-08-2012
Ben Bacarisse於 2011年12月29日星期四UTC+8下午7時58分14 寫道:
> Stone <(E-Mail Removed)> writes:
>
> > 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[i]) using data[ptr[i]] 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[i], idx[i], data[idx[i]]);
> }
>
> 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".
>
> --
> Ben.


This will turn the quick sort algorithm to be of O(nlog(n)) in speed
and O(n) used for the heap space.

Thus the non-choking merge sort is a distributed system is better.

Of course sorting integers of 32 bits in a radix sort of billions of items
in an 64 bit OS is the obvious way to replace the quick sort in the standard
library of C.

An array of 32 bit integers can be decomposed as 12-12-8 in 3 passes or 16-16 in two passes in a descent radix sort implementation that needs the O(n) chunk
in the heap space.

 
Reply With Quote
 
 
 
 
Ben Bacarisse
Guest
Posts: n/a
 
      01-08-2012
pete <(E-Mail Removed)> writes:

> 88888 Dihedral wrote:

<snip>
>> This will turn the quick sort algorithm to be of O(nlog(n)) in speed
>> and O(n) used for the heap space.

>
> First of all,
> whether or not qsort uses the quicksort algorithm,
> is up to the implementation.


It's up to you, of course, but there doesn't seem to be much point in
correcting 88888 Dihedral's posts. They seem to consist of random
truths and falsehoods only tangentially related to the posting.

> Second,
> quicksort can be implemented with O(1) use of memory.


I think this is an abuse of notation. Since you post C code to back
this up, I presume that you are saying that quicksort's maximum memory
usage is reasonably small and can be predicted (indeed it can be) but
that's not what O(1) means. The memory usage of all implementations of
all sort algorithms is bounded above by a constant (maybe the number of
particles in the universe) so big O is not very helpful here.

<snip>
> struct {
> size_t bytes;
> void *base;
> } stack[CHAR_BIT * sizeof nmemb], *stack_ptr;

<snip>

The abstract algorithm whose code you posted uses O(log n) stack space.

--
Ben.
 
Reply With Quote
 
 
 
 
88888 Dihedral
Guest
Posts: n/a
 
      01-08-2012
Ben Bacarisse於 2012年1月8日星期日UTC+8下午8時50分49秒 道:
> pete
> writes:
>
> > 88888 Dihedral wrote:

> <snip>
> >> This will turn the quick sort algorithm to be of O(nlog(n)) in speed
> >> and O(n) used for the heap space.

> >
> > First of all,
> > whether or not qsort uses the quicksort algorithm,
> > is up to the implementation.

>
> It's up to you, of course, but there doesn't seem to be much point in
> correcting 88888 Dihedral's posts. They seem to consist of random
> truths and falsehoods only tangentially related to the posting.
>
> > Second,
> > quicksort can be implemented with O(1) use of memory.


Are you joking for nonsense again?

Feeding a quick sort with a segment of 3,4,5,6 repeated for 2 to 10 thousand
times, then the quick sort will be choked to be so slow.

A non-choking quick sort is of O(nlog(n)) in time spend
for sorting arbitrary n items even in the worst case.














>
> I think this is an abuse of notation. Since you post C code to back
> this up, I presume that you are saying that quicksort's maximum memory
> usage is reasonably small and can be predicted (indeed it can be) but
> that's not what O(1) means. The memory usage of all implementations of
> all sort algorithms is bounded above by a constant (maybe the number of
> particles in the universe) so big O is not very helpful here.
>
> <snip>
> > struct {
> > size_t bytes;
> > void *base;
> > } stack[CHAR_BIT * sizeof nmemb], *stack_ptr;

> <snip>
>
> The abstract algorithm whose code you posted uses O(log n) stack space.
>
> --
> Ben.


 
Reply With Quote
 
Phil Carmody
Guest
Posts: n/a
 
      01-17-2012
pete <(E-Mail Removed)> writes:
> Second,
> quicksort can be implemented with O(1) use of memory.


If you were going to make such a statement, why stop at quicksort?

Anything which only needs to accept a bounded amount of input can
be implemented with O(1) use of memory.

Phil
--
Unix is simple. It just takes a genius to understand its simplicity
-- Dennis Ritchie (1941-2011), Unix Co-Creator
 
Reply With Quote
 
 
 
Reply

Thread Tools

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 Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
is there a way to refer to public properties in other user controls Web Search Store ASP .Net Web Controls 11 04-23-2008 07:00 PM
is there a way to refer to public properties in other user controls Web Search Store ASP .Net Web Services 11 04-23-2008 07:00 PM
is there a way to refer to public properties in other user controls Web Search Store ASP .Net 11 04-23-2008 07:00 PM
501 PIX "deny any any" "allow any any" Any Anybody? Networking Student Cisco 4 11-16-2006 10:40 PM
is there a quick way to compare the results from two arrays and note the diffences? windandwaves HTML 1 03-24-2005 09:49 PM



Advertisments