Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #15162 > unrolled thread

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

Back to article view | Back to comp.lang.c

Contents

  Is there any way to refer to another array in qsort's compare function? Stone <stonekyx@gmail.com> - 2011-12-29 00:27 -0800
    Re: Is there any way to refer to another array in qsort's compare function? Dr Nick <3-nospam@temporary-address.org.uk> - 2011-12-29 08:57 +0000
    Re: Is there any way to refer to another array in qsort's compare function? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-12-29 11:58 +0000
      Re: Is there any way to refer to another array in qsort's compare function? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-29 04:20 -0800
        Re: Is there any way to refer to another array in qsort's compare function? Dr Nick <3-nospam@temporary-address.org.uk> - 2011-12-29 12:37 +0000
          Re: Is there any way to refer to another array in qsort's compare function? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-29 04:48 -0800
            Re: Is there any way to refer to another array in qsort's compare function? Dr Nick <3-nospam@temporary-address.org.uk> - 2011-12-29 12:59 +0000
              Re: Is there any way to refer to another array in qsort's compare function? Geoff <geoff@invalid.invalid> - 2011-12-29 10:09 -0800
                Re: Is there any way to refer to another array in qsort's compare function? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-29 17:50 -0800
                  Re: Is there any way to refer to another array in qsort's compare function? Geoff <geoff@invalid.invalid> - 2011-12-29 19:29 -0800
                    Re: Is there any way to refer to another array in qsort's compare function? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-30 00:36 -0800
                      Re: Is there any way to refer to another array in qsort's compare function? Bull in a China Blue Shop <chine.bleu@yahoo.com> - 2011-12-30 00:52 -0800
                        Re: Is there any way to refer to another array in qsort's compare function? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-30 02:16 -0800
                Re: Is there any way to refer to another array in qsort's compare function? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-29 18:01 -0800
              Re: Is there any way to refer to another array in qsort's compare function? James Kuyper <jameskuyper@verizon.net> - 2011-12-29 13:21 -0500
          Re: Is there any way to refer to another array in qsort's compare function? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-30 23:18 -0800
      Re: Is there any way to refer to another array in qsort's compare function? 88888 Dihedral <dihedral88888@googlemail.com> - 2012-01-07 23:40 -0800
        Re: Is there any way to refer to another array in qsort's compare function? pete <pfiland@mindspring.com> - 2012-01-08 07:26 -0500
          Re: Is there any way to refer to another array in qsort's compare function? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2012-01-08 12:50 +0000
            Re: Is there any way to refer to another array in qsort's compare function? 88888 Dihedral <dihedral88888@googlemail.com> - 2012-01-08 06:02 -0800
          Re: Is there any way to refer to another array in qsort's compare function? Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2012-01-17 12:35 +0200
    Re: Is there any way to refer to another array in qsort's compare function? Bull in a China Blue Shop <chine.bleu@yahoo.com> - 2011-12-29 05:07 -0800
      Re: Is there any way to refer to another array in qsort's compare function? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-12-29 14:16 +0000
        Re: Is there any way to refer to another array in qsort's compare function? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2011-12-29 15:29 +0000
          Re: Is there any way to refer to another array in qsort's compare function? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-29 09:33 -0800
          Re: Is there any way to refer to another array in qsort's compare function? 88888 Dihedral <dihedral88888@googlemail.com> - 2011-12-29 15:40 -0800
    Re: Is there any way to refer to another array in qsort's compare function? James Kuyper <jameskuyper@verizon.net> - 2011-12-29 10:50 -0500
    Re: Is there any way to refer to another array in qsort's compare function? pete <pfiland@mindspring.com> - 2012-01-07 20:50 -0500

Page 1 of 2  [1] 2  Next page →

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

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?

Thanks&Regards.

Stone.

[toc] | [next] | [standalone]

#15163

Stone <stonekyx@gmail.com> 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?

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).
-- 
Online waterways route planner            | http://canalplan.eu
Plan trips, see photos, check facilities  | http://canalplan.org.uk

[toc] | [prev] | [next] | [standalone]

#15168

Stone <stonekyx@gmail.com> 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.

[toc] | [prev] | [next] | [standalone]

#15171

Ben Bacarisse於 2011年12月29日星期四UTC+8下午7時58分14秒寫道：
> Stone <ston...@gmail.com> 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 method uses more memory. Do you think that just 
overloading the comparison function by OOP can make it not choking at all?
 

[toc] | [prev] | [next] | [standalone]

#15172

88888 Dihedral <dihedral88888@googlemail.com> writes:

> Ben Bacarisse於 2011年12月29日星期四UTC+8下午7時58分14秒寫道：
>> Stone <ston...@gmail.com> 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".
>
> 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.
-- 
Online waterways route planner            | http://canalplan.eu
Plan trips, see photos, check facilities  | http://canalplan.org.uk

[toc] | [prev] | [next] | [standalone]

#15173

Dr Nick於 2011年12月29日星期四UTC+8下午8時37分26秒寫道：
> 88888 Dihedral <dihedr...@googlemail.com> writes:
> 
> > Ben Bacarisse於 2011年12月29日星期四UTC+8下午7時58分14秒寫道：
> >> Stone <sto...@gmail.com> 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".
> >
> > 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.
> -- 
> Online waterways route planner            | http://canalplan.eu
> Plan trips, see photos, check facilities  | http://canalplan.org.uk

  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. 

[toc] | [prev] | [next] | [standalone]

#15174

88888 Dihedral <dihedral88888@googlemail.com> writes:

> Dr Nick於 2011年12月29日星期四UTC+8下午8時37分26秒寫道：
>> 88888 Dihedral <dihedr...@googlemail.com> writes:
>> 
>> > Ben Bacarisse於 2011年12月29日星期四UTC+8下午7時58分14秒寫道：
>> >> Stone <sto...@gmail.com> 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".
>> >
>> > 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.
-- 
Online waterways route planner            | http://canalplan.eu
Plan trips, see photos, check facilities  | http://canalplan.org.uk

[toc] | [prev] | [next] | [standalone]

#15194

On Thu, 29 Dec 2011 12:59:35 +0000, Dr Nick
<3-nospam@temporary-address.org.uk> 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'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.

[toc] | [prev] | [next] | [standalone]

#15226

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 ?

[toc] | [prev] | [next] | [standalone]

#15228

On Thu, 29 Dec 2011 17:50:45 -0800 (PST), 88888 Dihedral
<dihedral88888@googlemail.com> wrote:

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

[toc] | [prev] | [next] | [standalone]

#15229

Geoff於 2011年12月30日星期五UTC+8上午11時29分17秒寫道：
> On Thu, 29 Dec 2011 17:50:45 -0800 (PST), 88888 Dihedral
> <dihedr...@googlemail.com> wrote:
> 
> >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.

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. 

[toc] | [prev] | [next] | [standalone]

#15230

In article <32323881.594.1325234172270.JavaMail.geo-discussion-forums@prfi34>,
 88888 Dihedral <dihedral88888@googlemail.com> wrote:

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

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.

[toc] | [prev] | [next] | [standalone]

#15232

Bull in a China Blue Shop於 2011年12月30日星期五UTC+8下午4時52分12秒寫道：
> In article <32323881.594.1325234172270.JavaMail.geo-discussion-forums@prfi34>,
>  88888 Dihedral <dihedr...@googlemail.com> wrote:
> 
> > 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. 
> 
> 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. 

[toc] | [prev] | [next] | [standalone]

#15227

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?    

[toc] | [prev] | [next] | [standalone]

#15195

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.

[toc] | [prev] | [next] | [standalone]

#15239

Dr Nick於 2011年12月29日星期四UTC+8下午8時37分26秒寫道：
> 88888 Dihedral <dihedr...@googlemail.com> writes:
> 
> > Ben Bacarisse於 2011年12月29日星期四UTC+8下午7時58分14秒寫道：
> >> Stone <sto...@gmail.com> 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".
> >
> > 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.
> -- 
> Online waterways route planner            | http://canalplan.eu
> Plan trips, see photos, check facilities  | http://canalplan.org.uk

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. 

[toc] | [prev] | [next] | [standalone]

#15568

Ben Bacarisse於 2011年12月29日星期四UTC+8下午7時58分14秒寫道：
> Stone <ston...@gmail.com> 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.  
 

[toc] | [prev] | [next] | [standalone]

#15581

88888 Dihedral wrote:
> 
> Ben Bacarisse於 2011年12月29日星期四UTC+8下午7時58分14秒寫道：
> > Stone <ston...@gmail.com> 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.

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

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

#include <stddef.h>
#include <limits.h>

void 
q_sort(void *base, size_t nmemb, size_t size, 
       int (*compar)(const void *, const void *))
{
    unsigned char *left;
    size_t middle, last, right;
    struct {
        size_t bytes;
        void *base;
    } stack[CHAR_BIT * sizeof nmemb], *stack_ptr;
    unsigned char *p1, *p2, *end, swap;  
 
    stack -> bytes = nmemb * size;
    stack -> base  = base;
    stack_ptr = stack + 1;
    do {
        --stack_ptr;
        if (stack_ptr -> bytes > size) {
            right = stack_ptr -> bytes - size;
            left = stack_ptr -> base;
            last = middle = 0;
            do {
                middle += size;
                if (compar(left, left + middle) > 0) {
                    last += size;
                    p1 = left + middle;
                    p2 = left + last;
                    end = p2 + size;
                    do {
                        swap  = *p1;
                        *p1++ = *p2;
                        *p2++ = swap;
                    } while (p2 != end);
                }
            } while (middle != right);
            p1 = left;
            p2 = left + last;
            end = p2 + size;
            do {
                swap  = *p1;
                *p1++ = *p2;
                *p2++ = swap;
            } while (p2 != end);
            if (right - last > last) {
                stack_ptr   -> base  = last + size + left;
                stack_ptr++ -> bytes = right - last;
                stack_ptr   -> base  = left;
                stack_ptr++ -> bytes = last;
            } else {
                stack_ptr++ -> bytes = last;
                stack_ptr   -> base  = last + size + left;
                stack_ptr++ -> bytes = right - last;
            }
        }
    } while (stack_ptr != stack);
}

-- 
pete

[toc] | [prev] | [next] | [standalone]

#15582

pete <pfiland@mindspring.com> 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.

[toc] | [prev] | [next] | [standalone]

#15584

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.

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.lang.c

csiph-web