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

qsort() standard functions

Started by	rick.c.hodgin@gmail.com
First post	2019-04-24 09:08 -0700
Last post	2019-05-04 05:53 -0700
Articles	20 on this page of 103 — 26 participants

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

  qsort() standard functions rick.c.hodgin@gmail.com - 2019-04-24 09:08 -0700
    Re: qsort() standard functions gazelle@shell.xmission.com (Kenny McCormack) - 2019-04-24 16:12 +0000
      Re: qsort() standard functions rick.c.hodgin@gmail.com - 2019-04-24 09:18 -0700
        Re: qsort() standard functions Chad <cdalten@gmail.com> - 2019-05-02 12:02 -0700
      Re: qsort() standard functions Real Troll <real.troll@trolls.com> - 2019-04-24 22:30 -0400
        Re: qsort() standard functions "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2019-04-24 19:32 -0700
          Re: qsort() standard functions Jorgen Grahn <grahn+nntp@snipabacken.se> - 2019-04-25 10:19 +0000
            Re: qsort() standard functions rick.c.hodgin@gmail.com - 2019-04-25 04:09 -0700
              Re: qsort() standard functions Richard Damon <Richard@Damon-Family.org> - 2019-04-25 08:13 -0400
                Re: qsort() standard functions fir <profesor.fir@gmail.com> - 2019-04-25 06:39 -0700
                Re: qsort() standard functions already5chosen@yahoo.com - 2019-04-25 07:23 -0700
        Re: qsort() standard functions fir <profesor.fir@gmail.com> - 2019-04-25 00:39 -0700
          Re: qsort() standard functions Real Troll <Real.Troll@Trolls.com> - 2019-04-25 23:27 +0100
    Re: qsort() standard functions John Bode <jfbode1029@gmail.com> - 2019-04-24 09:34 -0700
      Re: qsort() standard functions "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2019-04-24 09:47 -0700
      Re: qsort() standard functions John Bode <jfbode1029@gmail.com> - 2019-04-24 09:47 -0700
        Re: qsort() standard functions "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2019-04-24 12:54 -0400
          Re: qsort() standard functions John Bode <jfbode1029@gmail.com> - 2019-04-24 11:33 -0700
            Re: qsort() standard functions "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2019-04-24 14:41 -0400
              Re: qsort() standard functions John Bode <jfbode1029@gmail.com> - 2019-04-24 11:52 -0700
                Re: qsort() standard functions gazelle@shell.xmission.com (Kenny McCormack) - 2019-04-24 19:12 +0000
                Re: qsort() standard functions "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2019-04-24 16:05 -0400
                  Re: qsort() standard functions queequeg@trust.no1 (Queequeg) - 2019-04-24 20:39 +0000
              Re: qsort() standard functions James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-04-24 16:33 -0700
        Re: qsort() standard functions gazelle@shell.xmission.com (Kenny McCormack) - 2019-04-24 19:18 +0000
          Re: qsort() standard functions Bart <bc@freeuk.com> - 2019-04-24 20:28 +0100
            Re: qsort() standard functions gazelle@shell.xmission.com (Kenny McCormack) - 2019-04-24 21:27 +0000
          Re: qsort() standard functions fir <profesor.fir@gmail.com> - 2019-04-24 12:31 -0700
          Re: qsort() standard functions John Bode <jfbode1029@gmail.com> - 2019-04-24 13:02 -0700
            Re: qsort() standard functions fir <profesor.fir@gmail.com> - 2019-04-24 13:41 -0700
              Re: qsort() standard functions fir <profesor.fir@gmail.com> - 2019-04-24 14:00 -0700
                Re: qsort() standard functions Anton Shepelev <anton.txt@gmail.com> - 2019-04-25 00:22 +0300
                  Re: qsort() standard functions fir <profesor.fir@gmail.com> - 2019-04-24 15:04 -0700
                    Re: qsort() standard functions fir <profesor.fir@gmail.com> - 2019-04-24 15:20 -0700
                      Re: qsort() standard functions fir <profesor.fir@gmail.com> - 2019-04-24 15:40 -0700
                        Re: qsort() standard functions fir <profesor.fir@gmail.com> - 2019-04-24 15:57 -0700
                          Re: qsort() standard functions fir <profesor.fir@gmail.com> - 2019-04-24 16:06 -0700
                            Re: qsort() standard functions Anton Shepelev <anton.txt@gmail.com> - 2019-04-25 23:49 +0300
                              Re: qsort() standard functions Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-04-25 22:45 +0100
                                Re: qsort() standard functions Bart <bc@freeuk.com> - 2019-04-25 23:00 +0100
                                  Re: qsort() standard functions Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-04-25 23:24 +0100
                                Re: qsort() standard functions Real Troll <Real.Troll@Trolls.com> - 2019-04-25 23:20 +0100
                                Re: qsort() standard functions Anton Shepelev <anton.txt@g{oogle}mail.com> - 2019-04-26 13:06 +0300
                                  Re: qsort() standard functions Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-04-26 13:38 +0100
                                    Re: qsort() standard functions Anton Shepelev <anton.txt@g{oogle}mail.com> - 2019-04-26 16:43 +0300
                                      Re: qsort() standard functions Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-04-26 17:46 +0100
                                        Re: qsort() standard functions Anton Shepelev <anton.txt@gmail.com> - 2019-04-27 14:55 +0300
                                          Re: qsort() standard functions Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-04-27 14:59 +0100
                                            Re: qsort() standard functions Robert Wessel <robertwessel2@yahoo.com> - 2019-04-27 11:41 -0500
                                              Re: qsort() standard functions Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-05-02 09:46 -0700
                                                Re: qsort() standard functions Anton Shepelev <anton.txt@gmail.com> - 2019-05-02 20:35 +0300
                                                  Re: qsort() standard functions fir <profesor.fir@gmail.com> - 2019-05-02 15:35 -0700
                                                    Re: qsort() standard functions fir <profesor.fir@gmail.com> - 2019-05-05 04:39 -0700
                                                  Re: qsort() standard functions Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-05-04 07:35 -0700
                                                    Re: qsort() standard functions Anton Shepelev <anton.txt@gmail.com> - 2019-05-05 00:01 +0300
                                            Re: qsort() standard functions Anton Shepelev <anton.txt@gmail.com> - 2019-05-02 15:11 +0300
                                              Re: qsort() standard functions Ben Bacarisse <ben.usenet@bsb.me.uk> - 2019-05-02 16:36 +0100
                                Re: qsort() standard functions Anton Shepelev <anton.txt@gmail.com> - 2019-04-27 14:47 +0300
                                  Re: qsort() standard functions Robert Wessel <robertwessel2@yahoo.com> - 2019-04-27 08:30 -0500
                                    Re: qsort() standard functions Anton Shepelev <anton.txt@gmail.com> - 2019-05-02 14:52 +0300
                                      Re: qsort() standard functions Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-05-04 07:13 -0700
                                        Re: qsort() standard functions Anton Shepelev <anton.txt@gmail.com> - 2019-05-05 22:57 +0300
                                          Re: qsort() standard functions David Brown <david.brown@hesbynett.no> - 2019-05-06 10:09 +0200
                                          Re: qsort() standard functions Tim Rentsch <tr.17687@z991.linuxsc.com> - 2019-06-01 05:22 -0700
                              Re: qsort() standard functions fir <profesor.fir@gmail.com> - 2019-04-25 17:09 -0700
                                Re: qsort() standard functions Bart <bc@freeuk.com> - 2019-04-26 10:58 +0100
                                  Re: qsort() standard functions mark.bluemel@gmail.com - 2019-04-26 03:59 -0700
                                  Re: qsort() standard functions fir <profesor.fir@gmail.com> - 2019-04-26 06:34 -0700
                                    Re: qsort() standard functions fir <profesor.fir@gmail.com> - 2019-04-26 07:16 -0700
                                      Re: qsort() standard functions fir <profesor.fir@gmail.com> - 2019-04-26 07:45 -0700
                                        Re: qsort() standard functions fir <profesor.fir@gmail.com> - 2019-04-26 08:29 -0700
                                Re: qsort() standard functions fir <profesor.fir@gmail.com> - 2019-04-26 12:06 -0700
                                  Re: qsort() standard functions fir <profesor.fir@gmail.com> - 2019-04-26 13:09 -0700
                                    Re: qsort() standard functions fir <profesor.fir@gmail.com> - 2019-04-26 13:37 -0700
                                      Re: qsort() standard functions fir <profesor.fir@gmail.com> - 2019-04-26 14:05 -0700
                      Re: qsort() standard functions Anton Shepelev <anton.txt@gmail.com> - 2019-04-27 14:59 +0300
                        Re: qsort() standard functions fir <profesor.fir@gmail.com> - 2019-04-27 06:19 -0700
                          Re: qsort() standard functions fir <profesor.fir@gmail.com> - 2019-04-27 06:32 -0700
    Re: qsort() standard functions Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2019-04-24 10:54 -0600
      Re: qsort() standard functions "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2019-04-24 10:10 -0700
      Re: qsort() standard functions Anton Shepelev <anton.txt@gmail.com> - 2019-04-25 00:06 +0300
    Re: qsort() standard functions scott@slp53.sl.home (Scott Lurndal) - 2019-04-24 17:37 +0000
      Re: qsort() standard functions "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2019-04-24 10:56 -0700
        Re: qsort() standard functions Joe Pfeiffer <pfeiffer@cs.nmsu.edu> - 2019-04-24 12:12 -0600
          Re: qsort() standard functions "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2019-04-24 14:27 -0400
            Re: qsort() standard functions John Bode <jfbode1029@gmail.com> - 2019-04-24 11:44 -0700
              Re: qsort() standard functions fir <profesor.fir@gmail.com> - 2019-04-24 11:57 -0700
                Re: qsort() standard functions fir <profesor.fir@gmail.com> - 2019-04-24 12:04 -0700
              Re: qsort() standard functions nobody@example.org (Scott) - 2019-04-25 01:16 +0000
                Re: qsort() standard functions James Kuyper <jameskuyper@alumni.caltech.edu> - 2019-04-24 21:38 -0400
    Re: qsort() standard functions "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2019-04-24 14:42 -0400
      Re: qsort() standard functions David Brown <david.brown@hesbynett.no> - 2019-04-24 22:13 +0200
      Re: qsort() standard functions queequeg@trust.no1 (Queequeg) - 2019-04-24 20:46 +0000
    Re: qsort() standard functions jadill33@gmail.com - 2019-04-24 14:01 -0700
    Re: qsort() standard functions "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2019-04-24 15:41 -0700
    Re: qsort() standard functions "Mr. Man-wai Chang" <toylet.toylet@gmail.com> - 2019-04-26 22:24 +0800
      Re: qsort() standard functions Anton Shepelev <anton.txt@gmail.com> - 2019-05-02 15:05 +0300
        Re: qsort() standard functions "Mr. Man-wai Chang" <toylet.toylet@gmail.com> - 2019-05-03 17:02 +0800
          Re: qsort() standard functions Chad <cdalten@gmail.com> - 2019-05-03 10:10 -0700
            Re: qsort() standard functions "Mr. Man-wai Chang" <toylet.toylet@gmail.com> - 2019-05-04 01:22 +0800
              Re: qsort() standard functions Chad <cdalten@gmail.com> - 2019-05-03 15:14 -0700
                [OT]Eternal.... programmer? "Mr. Man-wai Chang" <toylet.toylet@gmail.com> - 2019-05-04 06:20 +0800
                  Re: [OT]Eternal.... programmer? Chad <cdalten@gmail.com> - 2019-05-04 05:53 -0700

Page 3 of 6 — ← Prev page 1 2 [3] 4 5 6 Next page →

#143443

From	Ben Bacarisse <ben.usenet@bsb.me.uk>
Date	2019-04-25 23:24 +0100
Message-ID	<878svxu3je.fsf@bsb.me.uk>
In reply to	#143441

Bart <bc@freeuk.com> writes:

> On 25/04/2019 22:45, Ben Bacarisse wrote:
>> Anton Shepelev <anton.txt@gmail.com> writes:
>
>> I don't want to be overly negative -- you are one of the few people who
>> posts actual code here.  I really liked your sort function.
>
> Did you get the main sort module to work?

Yes.

> I couldn't get it to do that, either with my own test code, or the
> code that was posted an hour ago.

I also wrote a small driver and everything worked, though I did not test
that much.

-- 
Ben.

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

#143442

From	Real Troll <Real.Troll@Trolls.com>
Date	2019-04-25 23:20 +0100
Message-ID	<q9tbsg$1jei$1@gioia.aioe.org>
In reply to	#143440

On 25/04/2019 22:45, Ben Bacarisse wrote:
>
> you are one of the few people who
> posts actual code here.

but we also have that Peter Popoff look alike who keeps telling us (here 
on C & C++ newsgroups) that Jesus will solve all the problems of the 
world without getting out your bed!!!!.

<https://www.youtube.com/watch?v=x_NuZDaR46I>

>

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

#143448

From	Anton Shepelev <anton.txt@g{oogle}mail.com>
Date	2019-04-26 13:06 +0300
Message-ID	<20190426130638.ee2504b98c14cb6c666f95b8@g{oogle}mail.com>
In reply to	#143440

Ben Bacarisse:

>You play fast and loose with types here!  One case prevents
>compilation and there is also an int overflow bug that
>really matters.

Thanks for your comments.  I wrote it in a hurry and shall
have to post a fixed corrected version.  It is a shame,
though, that the compiler did not report any errors.

>> /* comparison function: */
>> int comp( void * data, int i, int j )
>> {  return ( (int*)data )[i] -
>>           ( (int*)data )[j];
>> }
>
>Your header specifies a fourth parameter:
>
>  typedef int  (*comp_f)( void * data, int i, int j, const void * extra );

Yes, it is missing.

>Also, did you mean for the "const"s to be the other way
>round?
>  typedef int (*comp_f)(const void *data, int i, int j, void * extra);

No.  The extra data (`extra') should not be modified in the
process of sorting, whereas the data to sort (`data')
should.  This `extra' parameter may point to whatever
additional information the user wants to supply.  When
sorting a table, for example, it may contain the column by
which to sort and the order (ascending or descending).

>(I'd use size_t for all the offsets but not doing that is
>presumably a deliberate decision on your part.)

Yes, the temptation to use int universally for all integer
values.

>>/* comparison function for standard qsort: */
>>compar(const void * a, void * b)
>>{  return *((int*)a) - *((int*)b);
>>}
>
>qsort wants both pointers to point to const void.  Also,
>this declaration uses implicit int, but I think you said
>you write C90.  Mind you, adding the return type is, to my
>mind, good practise even in C90.

Don't know why I wrote it so carelessly.  Of course, the
arguments are symmetrical and should both be modified by
`const'.  The lack of a return type is also just an error on
my part.

>>/* swap function: */
>>void swap( void * data, int i, int j )
>>{  int buf;
>>   buf = ( (int[])data )[i];
>>   ( (int*)data )[i] = ( (int*)data )[j];
>>   ( (int*)data )[j] = buf;
>>}
>
>You can't cast to an array type, nor to an incomplete type;
>int [] is both!

Therefore,

  buf = (int*)data )[i]

In a hurry I forgot that outside parameter declarations,
int[] is different from int*.

>Subtracting ints can lead to unintended behaviour when the
>result overflows, even when the actual behaviour is the
>expected "wrap-around" one.

True, and that seemed the laziest (and efficient) way to
implement a comparison function.  I will reconsider.

>I don't want to be overly negative -- you are one of the
>few people who posts actual code here.  I really liked your
>sort function.

No, I am greateful for your reply, and will be back.

-- 
()  ascii ribbon campaign - against html e-mail
/\  http://preview.tinyurl.com/qcy6mjc [archived]

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

#143453

From	Ben Bacarisse <ben.usenet@bsb.me.uk>
Date	2019-04-26 13:38 +0100
Message-ID	<87mukdrler.fsf@bsb.me.uk>
In reply to	#143448

Anton Shepelev <anton.txt@g{oogle}mail.com> writes:

> Ben Bacarisse:
<cut>
>> ... did you mean for the "const"s to be the other way
>> round?
>>  typedef int (*comp_f)(const void *data, int i, int j, void * extra);
>
> No.  The extra data (`extra') should not be modified in the
> process of sorting, whereas the data to sort (`data')
> should.  This `extra' parameter may point to whatever
> additional information the user wants to supply.  When
> sorting a table, for example, it may contain the column by
> which to sort and the order (ascending or descending).

Hmm... I think that's wrong (about what's const and what isn't).  The
data items should /not/ be modified simply by the act of comparing one
to another, but the extra data might very well be.  For example, I've
done collection of statistics via the 'extra' data pointer.

<cut>
-- 
Ben.

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

#143458

From	Anton Shepelev <anton.txt@g{oogle}mail.com>
Date	2019-04-26 16:43 +0300
Message-ID	<20190426164329.8cd319730cce76ab734f5ac6@g{oogle}mail.com>
In reply to	#143453

Ben Bacarisse:

>>>Also, did you mean for the "const"s to be the other way
>>>round?
>>>  typedef int (*comp_f)(const void *data, int i, int j, void * extra);
>>
>>No.  The extra data (`extra') should not be modified in
>>the process of sorting, whereas the data to sort (`data')
>>should.  This `extra' parameter may point to whatever
>>additional information the user wants to supply.  When
>>sorting a table, for example, it may contain the column by
>>which to sort
>
>Hmm... I think that's wrong (about what's const and what
>isn't).  The data items should /not/ be modified simply by
>the act of comparing one to another,

But they are modified in swap_f, and I intended to make the
parameter type the same throughout.  It is better to accept
a `void *' and pass on as `const void *' to the comparison
function.

>but the extra data might very well be.  For example, I've
>done collection of statistics via the 'extra' data pointer.

This is the only case of modifying `extra' that I could
think of, but it belongs more to debugging than to actual
use, so I didn't provide it.  Not a big deal if I do,
though, except if one is a devotee of const correctness...

-- 
()  ascii ribbon campaign - against html e-mail
/\  http://preview.tinyurl.com/qcy6mjc [archived]

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

#143467

From	Ben Bacarisse <ben.usenet@bsb.me.uk>
Date	2019-04-26 17:46 +0100
Message-ID	<87ef5osoib.fsf@bsb.me.uk>
In reply to	#143458

Anton Shepelev <anton.txt@g{oogle}mail.com> writes:

> Ben Bacarisse:
>
>>>>Also, did you mean for the "const"s to be the other way
>>>>round?
>>>>  typedef int (*comp_f)(const void *data, int i, int j, void * extra);
>>>
>>>No.  The extra data (`extra') should not be modified in
>>>the process of sorting, whereas the data to sort (`data')
>>>should.  This `extra' parameter may point to whatever
>>>additional information the user wants to supply.  When
>>>sorting a table, for example, it may contain the column by
>>>which to sort
>>
>>Hmm... I think that's wrong (about what's const and what
>>isn't).  The data items should /not/ be modified simply by
>>the act of comparing one to another,
>
> But they are modified in swap_f, and I intended to make the
> parameter type the same throughout.

That, to me, is a false consistency.  The two functions are not the
same.  A swap function has to modify the pointer targets, a comparison
function should not.

> It is better to accept
> a `void *' and pass on as `const void *' to the comparison
> function.

I don't understand this.

>>but the extra data might very well be.  For example, I've
>>done collection of statistics via the 'extra' data pointer.
>
> This is the only case of modifying `extra' that I could
> think of, but it belongs more to debugging than to actual
> use, so I didn't provide it.

I think it's better to consider what's logical rather than what you (or
I) can think of.  But there are certainly other uses of non-const target
extra data.

> Not a big deal if I do,
> though, except if one is a devotee of const correctness...

Again, I'm not side what you mean here.  It seems as if you are saying
that if you did make 'extra' a 'const void *', that would annoy devotees
of const correctness.  Seems like the other way round to me, but many
I've missed your meaning.

-- 
Ben.

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

#143485

From	Anton Shepelev <anton.txt@gmail.com>
Date	2019-04-27 14:55 +0300
Message-ID	<20190427145541.4f9f1d28cc434e9136029307@gmail.com>
In reply to	#143467

Ben Bacarisse to Anton Shepelev:

> > > Hmm... I think that's wrong (about what's const and
> > > what isn't).  The data items should /not/ be modified
> > > simply by the act of comparing one to another,
> >
> > But they are modified in swap_f, and I intended to make
> > the parameter type the same throughout.
>
> That, to me, is a false consistency.  The two functions
> are not the same.  A swap function has to modify the
> pointer targets, a comparison function should not.

Agreed (and fixed).

> > It is better to accept a `void *' and pass on as `const
> > void *' to the comparison function.
>
> I don't understand this.

I meant: "and pass *it* on as `const void *'".

> > This is the only case of modifying `extra' that I could
> > think of, but it belongs more to debugging than to
> > actual use, so I didn't provide it.
>
> I think it's better to consider what's logical rather than
> what you (or I) can think of.  But there are certainly
> other uses of non-const target extra data.

If so, you might want to have `extra' not only in the
comparison function but also in the swap function, in order
for example to gather statistics about the number of swap
operations.

> > Not a big deal if I do, though, except if one is a
> > devotee of const correctness...
>
> Again, I'm not side what you mean here.  It seems as if
> you are saying that if you did make 'extra' a 'const void
> *', that would annoy devotees of const correctness.  Seems
> like the other way round to me, but many I've missed your
> meaning.

I meant avoiding `const' before `extra' for the rare case of
debugging and gathering statistics whereas in actual use
`extra' is very unlikely to change.

-- 
()  ascii ribbon campaign -- against html e-mail
/\  http://preview.tinyurl.com/qcy6mjc [archived]

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

#143492

From	Ben Bacarisse <ben.usenet@bsb.me.uk>
Date	2019-04-27 14:59 +0100
Message-ID	<878svvsg52.fsf@bsb.me.uk>
In reply to	#143485

Anton Shepelev <anton.txt@gmail.com> writes:

> Ben Bacarisse to Anton Shepelev:
<cut>
>> I think it's better to consider what's logical rather than
>> what you (or I) can think of.  But there are certainly
>> other uses of non-const target extra data.
>
> If so, you might want to have `extra' not only in the
> comparison function but also in the swap function, in order
> for example to gather statistics about the number of swap
> operations.

That's an interesting thought.  Yes, in a language without first-class
functions it is probably wise to pass some context pointer to every
call-back at least in general-purpose utilities like sorting.

>> > Not a big deal if I do, though, except if one is a
>> > devotee of const correctness...
>>
>> Again, I'm not [sure] what you mean here.  It seems as if
>> you are saying that if you did make 'extra' a 'const void
>> *', that would annoy devotees of const correctness.  Seems
>> like the other way round to me, but many I've missed your
>> meaning.
>
> I meant avoiding `const' before `extra' for the rare case of
> debugging and gathering statistics whereas in actual use
> `extra' is very unlikely to change.

I can see you won't be persuaded, but it's not about 'avoiding' const,
it's about const being, in my opinion, wrong.  To take another example,
if the comparison is expensive, you might want to store some derived key
in the extra data.

-- 
Ben.

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

#143494

From	Robert Wessel <robertwessel2@yahoo.com>
Date	2019-04-27 11:41 -0500
Message-ID	<c919ce5osb9vloiag3ugnusnjf40191gr2@4ax.com>
In reply to	#143492

On Sat, 27 Apr 2019 14:59:37 +0100, Ben Bacarisse
<ben.usenet@bsb.me.uk> wrote:

>Anton Shepelev <anton.txt@gmail.com> writes:
>
>> Ben Bacarisse to Anton Shepelev:
><cut>
>>> I think it's better to consider what's logical rather than
>>> what you (or I) can think of.  But there are certainly
>>> other uses of non-const target extra data.
>>
>> If so, you might want to have `extra' not only in the
>> comparison function but also in the swap function, in order
>> for example to gather statistics about the number of swap
>> operations.
>
>That's an interesting thought.  Yes, in a language without first-class
>functions it is probably wise to pass some context pointer to every
>call-back at least in general-purpose utilities like sorting.
>
>>> > Not a big deal if I do, though, except if one is a
>>> > devotee of const correctness...
>>>
>>> Again, I'm not [sure] what you mean here.  It seems as if
>>> you are saying that if you did make 'extra' a 'const void
>>> *', that would annoy devotees of const correctness.  Seems
>>> like the other way round to me, but many I've missed your
>>> meaning.
>>
>> I meant avoiding `const' before `extra' for the rare case of
>> debugging and gathering statistics whereas in actual use
>> `extra' is very unlikely to change.
>
>I can see you won't be persuaded, but it's not about 'avoiding' const,
>it's about const being, in my opinion, wrong.  To take another example,
>if the comparison is expensive, you might want to store some derived key
>in the extra data.


I don't really have a strong opinion either way, but since the "extra"
area is provided and used (only) by the user of the sort function, I'm
not so sure that requiring the user to cast away the const-ness, if
the user wants that, is really all that wrong.  This is in keeping
with the not uncommon practice of objects that have hidden state still
being treated as "const" in many contexts.

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

#143572

From	Tim Rentsch <tr.17687@z991.linuxsc.com>
Date	2019-05-02 09:46 -0700
Message-ID	<86h8acg5y5.fsf@mailhub.linuxsc.com>
In reply to	#143494

Robert Wessel <robertwessel2@yahoo.com> writes:

> On Sat, 27 Apr 2019 14:59:37 +0100, Ben Bacarisse
> <ben.usenet@bsb.me.uk> wrote:
>
>> Anton Shepelev <anton.txt@gmail.com> writes:
>>
>>> Ben Bacarisse to Anton Shepelev:
>>
>> <cut>
>>
>>>> I think it's better to consider what's logical rather than
>>>> what you (or I) can think of.  But there are certainly
>>>> other uses of non-const target extra data.
>>>
>>> If so, you might want to have `extra' not only in the
>>> comparison function but also in the swap function, in order
>>> for example to gather statistics about the number of swap
>>> operations.
>>
>> That's an interesting thought.  Yes, in a language without
>> first-class functions it is probably wise to pass some context
>> pointer to every call-back at least in general-purpose utilities
>> like sorting.
>>
>>>>> Not a big deal if I do, though, except if one is a
>>>>> devotee of const correctness...
>>>>
>>>> Again, I'm not [sure] what you mean here.  It seems as if
>>>> you are saying that if you did make 'extra' a 'const void
>>>> *', that would annoy devotees of const correctness.  Seems
>>>> like the other way round to me, but many I've missed your
>>>> meaning.
>>>
>>> I meant avoiding `const' before `extra' for the rare case of
>>> debugging and gathering statistics whereas in actual use
>>> `extra' is very unlikely to change.
>>
>> I can see you won't be persuaded, but it's not about 'avoiding'
>> const, it's about const being, in my opinion, wrong.  To take
>> another example, if the comparison is expensive, you might want to
>> store some derived key in the extra data.
>
> I don't really have a strong opinion either way, but since the
> "extra" area is provided and used (only) by the user of the sort
> function, I'm not so sure that requiring the user to cast away the
> const-ness, if the user wants that, is really all that wrong.  This
> is in keeping with the not uncommon practice of objects that have
> hidden state still being treated as "const" in many contexts.

My reaction is very much the opposite.  The point of providing the
'extra' parameter is for the convenience of the client, and so
should accommodate as wide a range of use cases as it reasonably
can.  We do not know that a client data area will be used only
with calls to the sort function - it might be used in conjunction
with several different callback functions, for all sorts (no pun
intended) of purposes.  Furthermore the combination of a function
pointer and a void * pointer is a common idiom in C to provide the
functionality of a closure.  Surely the idiom expects that data
in the "closure" might be modified, and so a 'void *' type rather
than a 'const void *' type is more usual, and more appropriate.
Since the 'extra' parameter (almost always) needs to be converted
by the callback function, that function can choose a 'const Foo *'
type if const-ness is important there.  Forcing client code to put
in an unnecessary cast says in effect the sort routine knows better
than its callers.  Service routines such as sort should accommodate
their callers, not the other way around.

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

#143574

From	Anton Shepelev <anton.txt@gmail.com>
Date	2019-05-02 20:35 +0300
Message-ID	<20190502203521.9f93e01e3aa66851ce1ebfd3@gmail.com>
In reply to	#143572

Tim Rentsch:

> My reaction is very much the opposite.  The point of
> providing the 'extra' parameter is for the convenience of
> the client, and so should accommodate as wide a range of
> use cases as it reasonably can.  We do not know that a
> client data area will be used only with calls to the sort
> function - it might be used in conjunction with several
> different callback functions, for all sorts (no pun
> intended) of purposes.

You mean the data to which a pointer is passed to the sort
routing as the `extra' parameter can also be used elsewhere
in the program outside the sort routine?  If so, the `const'
modifier in the sort routine does not in any away affect
these other usages, does it?

> Furthermore the combination of a function pointer and a
> void * pointer is a common idiom in C to provide the
> functionality of a closure.  Surely the idiom expects that
> data in the "closure" might be modified, and so a 'void *'
> type rather than a 'const void *' type is more usual, and
> more appropriate.  Since the 'extra' parameter (almost
> always) needs to be converted by the callback function,
> that function can choose a 'const Foo *' type if const-
> ness is important there.  Forcing client code to put in an
> unnecessary cast says in effect the sort routine knows
> better than its callers.  Service routines such as sort
> should accommodate their callers, not the other way
> around.

I understand your appeal to generality but miss your point
about the unnecessary cast.  The cast is always there,
whether to `Foo *' or to `const Foo *'.  I should say it is
unavoidable rather than unnecessary.

-- 
()  ascii ribbon campaign -- against html e-mail
/\  http://preview.tinyurl.com/qcy6mjc [archived]

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

#143576

From	fir <profesor.fir@gmail.com>
Date	2019-05-02 15:35 -0700
Message-ID	<d48f64fe-d394-44cc-95df-c655a62cb7fb@googlegroups.com>
In reply to	#143574

W dniu czwartek, 2 maja 2019 19:35:32 UTC+2 użytkownik Anton Shepelev napisał:
> Tim Rentsch:
> 
> > My reaction is very much the opposite.  The point of
> > providing the 'extra' parameter is for the convenience of
> > the client, and so should accommodate as wide a range of
> > use cases as it reasonably can.  We do not know that a
> > client data area will be used only with calls to the sort
> > function - it might be used in conjunction with several
> > different callback functions, for all sorts (no pun
> > intended) of purposes.
> 
> You mean the data to which a pointer is passed to the sort
> routing as the `extra' parameter can also be used elsewhere
> in the program outside the sort routine?  If so, the `const'
> modifier in the sort routine does not in any away affect
> these other usages, does it?
> 
> > Furthermore the combination of a function pointer and a
> > void * pointer is a common idiom in C to provide the
> > functionality of a closure.  Surely the idiom expects that
> > data in the "closure" might be modified, and so a 'void *'
> > type rather than a 'const void *' type is more usual, and
> > more appropriate.  Since the 'extra' parameter (almost
> > always) needs to be converted by the callback function,
> > that function can choose a 'const Foo *' type if const-
> > ness is important there.  Forcing client code to put in an
> > unnecessary cast says in effect the sort routine knows
> > better than its callers.  Service routines such as sort
> > should accommodate their callers, not the other way
> > around.
> 
> I understand your appeal to generality but miss your point
> about the unnecessary cast.  The cast is always there,
> whether to `Foo *' or to `const Foo *'.  I should say it is
> unavoidable rather than unnecessary.
> 
it would be do to make real contest based on sorting - like what i said sort array of milion integer values 

when comparing real implementations not just staying at the "use quicksortt"

but as usual users here most often prefer talking something non important instead of focusing on core things

(and thats pity for me as i could learn something or tell something)

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

#143606

From	fir <profesor.fir@gmail.com>
Date	2019-05-05 04:39 -0700
Message-ID	<f2be0c91-1069-4b57-8279-8a8b719f0b71@googlegroups.com>
In reply to	#143576

W dniu piątek, 3 maja 2019 00:35:51 UTC+2 użytkownik fir napisał:
> W dniu czwartek, 2 maja 2019 19:35:32 UTC+2 użytkownik Anton Shepelev napisał:
> > Tim Rentsch:
> > 
> > > My reaction is very much the opposite.  The point of
> > > providing the 'extra' parameter is for the convenience of
> > > the client, and so should accommodate as wide a range of
> > > use cases as it reasonably can.  We do not know that a
> > > client data area will be used only with calls to the sort
> > > function - it might be used in conjunction with several
> > > different callback functions, for all sorts (no pun
> > > intended) of purposes.
> > 
> > You mean the data to which a pointer is passed to the sort
> > routing as the `extra' parameter can also be used elsewhere
> > in the program outside the sort routine?  If so, the `const'
> > modifier in the sort routine does not in any away affect
> > these other usages, does it?
> > 
> > > Furthermore the combination of a function pointer and a
> > > void * pointer is a common idiom in C to provide the
> > > functionality of a closure.  Surely the idiom expects that
> > > data in the "closure" might be modified, and so a 'void *'
> > > type rather than a 'const void *' type is more usual, and
> > > more appropriate.  Since the 'extra' parameter (almost
> > > always) needs to be converted by the callback function,
> > > that function can choose a 'const Foo *' type if const-
> > > ness is important there.  Forcing client code to put in an
> > > unnecessary cast says in effect the sort routine knows
> > > better than its callers.  Service routines such as sort
> > > should accommodate their callers, not the other way
> > > around.
> > 
> > I understand your appeal to generality but miss your point
> > about the unnecessary cast.  The cast is always there,
> > whether to `Foo *' or to `const Foo *'.  I should say it is
> > unavoidable rather than unnecessary.
> > 
> it would be do to make real contest based on sorting - like what i said sort array of milion integer values 
> 
> when comparing real implementations not just staying at the "use quicksortt"
> 
> but as usual users here most often prefer talking something non important instead of focusing on core things
> 
> (and thats pity for me as i could learn something or tell something)

anyway thios thread will back in future, i guess (becouse it is worth it)

(i mean topic of specifical array sorting codes in c with micro/milisecond ime measures, that beats other solutions)

so if not now - then later (i could discuss it right now but maybe some need to grow up to it, and im not enough 'motivated' to do it alone on my site and public results then (i got strong problems with 'motivation anyway, as i said))

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

#143592

From	Tim Rentsch <tr.17687@z991.linuxsc.com>
Date	2019-05-04 07:35 -0700
Message-ID	<86zho2i8yt.fsf@mailhub.linuxsc.com>
In reply to	#143574

Anton Shepelev <anton.txt@gmail.com> writes:

> Tim Rentsch:
>
>> My reaction is very much the opposite.  The point of
>> providing the 'extra' parameter is for the convenience of
>> the client, and so should accommodate as wide a range of
>> use cases as it reasonably can.  We do not know that a
>> client data area will be used only with calls to the sort
>> function - it might be used in conjunction with several
>> different callback functions, for all sorts (no pun
>> intended) of purposes.
>
> You mean the data to which a pointer is passed to the sort
> routing as the `extra' parameter can also be used elsewhere
> in the program outside the sort routine?

Yes, and in particular with other callback functions.

> If so, the `const'
> modifier in the sort routine does not in any away affect
> these other usages, does it?

My point is that one bears on the other and so, yes, it
can affect other code that needs the same callback data.


>> Furthermore the combination of a function pointer and a
>> void * pointer is a common idiom in C to provide the
>> functionality of a closure.  Surely the idiom expects that
>> data in the "closure" might be modified, and so a 'void *'
>> type rather than a 'const void *' type is more usual, and
>> more appropriate.  Since the 'extra' parameter (almost
>> always) needs to be converted by the callback function,
>> that function can choose a 'const Foo *' type if const-
>> ness is important there.  Forcing client code to put in an
>> unnecessary cast says in effect the sort routine knows
>> better than its callers.  Service routines such as sort
>> should accommodate their callers, not the other way
>> around.
>
> I understand your appeal to generality but miss your point
> about the unnecessary cast.  The cast is always there,
> whether to `Foo *' or to `const Foo *'.  I should say it is
> unavoidable rather than unnecessary.

When the parameter is const void * (but the use is not):

    int
    some_callback_1( const void *vdata  /*, other parameters */ ){
        Foo *data = (void *)vdata;
        /* ... rest of function ... */
        return  0;
    }

When the parameter is just void *, with no const (but the use is
const):

    int
    some_callback_2( void *vdata  /*, other parameters */ ){
        const Foo *data = vdata;
        /* ... rest of function ... */
        return  0;
    }

The first case needs a cast.  The second case doesn't need one,
and doesn't have one (and still wouldn't if the declaration were
'Foo *data = ...' without the 'const').

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

#143602

From	Anton Shepelev <anton.txt@gmail.com>
Date	2019-05-05 00:01 +0300
Message-ID	<20190505000109.359cbff1ce49cfb959796539@gmail.com>
In reply to	#143592

Tim Rentsch:

> When the parameter is const void * (but the use is not):
>
>     int
>     some_callback_1( const void *vdata  /*, other parameters */ ){
>         Foo *data = (void *)vdata;
>         /* ... rest of function ... */
>         return  0;
>     }
>
> When the parameter is just void *, with no const (but the
> use is const):
>
>     int
>     some_callback_2( void *vdata  /*, other parameters */ ){
>         const Foo *data = vdata;
>         /* ... rest of function ... */
>         return  0;
>     }
>
> The first case needs a cast.  The second case doesn't need
> one, and doesn't have one (and still wouldn't if the
> declaration were 'Foo *data = ...' without the 'const').

Ah, I had simply forgot about this automatic pointer
conversion because of lack of practice in C.

-- 
()  ascii ribbon campaign -- against html e-mail
/\  http://preview.tinyurl.com/qcy6mjc [archived]

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

#143569

From	Anton Shepelev <anton.txt@gmail.com>
Date	2019-05-02 15:11 +0300
Message-ID	<20190502151101.f8fce60bdd5749bc6a1c1fc7@gmail.com>
In reply to	#143492

Ben Bacarisse to Anton Shepelev:

> > I meant avoiding `const' before `extra' for the rare
> > case of debugging and gathering statistics whereas in
> > actual use `extra' is very unlikely to change.
>
> I can see you won't be persuaded, but it's not about
> 'avoiding' const, it's about const being, in my opinion,
> wrong.  To take another example, if the comparison is
> expensive, you might want to store some derived key in the
> extra data.

But I have already removed `const' and added one to `data',
exactly as you suggested:

   typedef int  (*comp_f)( const void * data, int i, int j, void * extra );
   [ http://al.howardknight.net/msgid.cgi?ID=155679895900 ]

-- 
()  ascii ribbon campaign -- against html e-mail
/\  http://preview.tinyurl.com/qcy6mjc [archived]

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

#143571

From	Ben Bacarisse <ben.usenet@bsb.me.uk>
Date	2019-05-02 16:36 +0100
Message-ID	<877eb8euli.fsf@bsb.me.uk>
In reply to	#143569

Anton Shepelev <anton.txt@gmail.com> writes:

> Ben Bacarisse to Anton Shepelev:
>
>> > I meant avoiding `const' before `extra' for the rare
>> > case of debugging and gathering statistics whereas in
>> > actual use `extra' is very unlikely to change.
>>
>> I can see you won't be persuaded, but it's not about
>> 'avoiding' const, it's about const being, in my opinion,
>> wrong.  To take another example, if the comparison is
>> expensive, you might want to store some derived key in the
>> extra data.
>
> But I have already removed `const' and added one to `data',
> exactly as you suggested:
>
>    typedef int  (*comp_f)( const void * data, int i, int j, void * extra );
>    [ http://al.howardknight.net/msgid.cgi?ID=155679895900 ]

I must have missed your agreement on this matter.  I seem to have got
lost in the words somewhere.

-- 
Ben.

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

#143484

From	Anton Shepelev <anton.txt@gmail.com>
Date	2019-04-27 14:47 +0300
Message-ID	<20190427144733.63852ec695135de51c951373@gmail.com>
In reply to	#143440

Here is a corrected version of my generic QuickSort implementation:

---------------------------------- sort.h --------------------------------------

/* ----------------------- A generic sorting routine ------------------------ */
/* Comparison function:
    > 0 <=> data[i] > data[j]
    < 0 <=> data[i] < data[j]
   == 0 <=> data[i] = data[j] */
typedef int  (*comp_f)( const void * data, int i, int j, void * extra );

/* Exchange ith and jth elements: */
typedef void (*swap_f)( void * data, int i, int j );

void sort
(  void * data, /* pointer to data to sort         */
   int    len,  /* length of data to sort          */
   comp_f comp, /* comparison function             */
   swap_f swap, /* swap function                   */
   void * extra /* user-supplied parameter to comp */
);

---------------------------------- sort.c --------------------------------------
#include <stdio.h>
#include <limits.h>
#include "sort.h"

/* Partition an array [l..r] around a "pivot" member so that */
/* the elements of the left sub-array do not exceed, and the ones */
/* of the right sub-array are not less than, the pivot. */
static int /* returns the right boundary of the left sub-array */
partition
(  void * data, /* pointer to the full array              */
   int    l,    /* left  boundary of the sub-array        */
   int    r,    /* right boundary of the sub-array, l < r */
   comp_f comp,
   swap_f swap,
   void * extra
)
{  int p; /* index of the pivot, element */
   p = ( l + r ) / 2; /* Chose the middle element as pivot */

   while( 1 )
   {  /* advance cursors until they stop at a pair of elements */
      /* that should be swapped or meet or go past each other.  */
      /* The pivot element serves as a sentinel.                */
      while( comp( data, l, p, extra ) < 0 ) l += 1;
      while( comp( data, r, p, extra ) > 0 ) r -= 1;
      if( l >= r ) break;

      swap( data, l, r );      /* Swap the pair found         */
           if( l == p ) p = r; /* Update pivot location if it */
      else if( r == p ) p = l; /* was changed during the swap */

      /* Advance the cursors. If they are adjecent they will cross: */
      l += 1; r -= 1;
   }
   return r;
}

void sort
(  void * data,
   int    len,
   comp_f comp,
   swap_f swap,
   void * extra
)
{  /* In this algorithm, minimun sufficient stack size is Log(len) */
   int sl[sizeof(int) * CHAR_BIT]; /* left  sub-array boundaries on the stack */
   int sr[sizeof(int) * CHAR_BIT]; /* right sub-array boundaries nn the stack */

   int d;          /* stack depth */
   int l, r;       /* left and right boundaries of a sub-array */
   int lpos, rpos; /* positions of the left and right new sub-arrays on the stack */
   int newr;       /* the right boundary of the new left sub-array */

   d     = 1; /* Put the initial sub-array onto the stack */
   sl[0] = 0; sr[0] = len - 1;   
   while( d > 0 )
   {  d -= 1; /* Take an element from the stack */
      l = sl[d]; r = sr[d];
      if( l >= r ) continue; /* Skip a subarray shorter than two */
      
      newr = partition( data, l , r, comp, swap, extra );

      /* process the shorter sub-array first to ease the stack: */
      lpos = d; rpos = d; 
      if( newr - l > r - newr - 1 ) rpos += 1;
      else                          lpos += 1;

      /* Put partiioned sub-arrays onto the stack: */
      sl[lpos] = l;        sr[lpos] = newr;
      sl[rpos] = newr + 1; sr[rpos] = r;
      d += 2;
   }
}

---------------------------------- test.c --------------------------------------

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "sort.h"

static void print( int * a, int n )
{  int i;
   for( i = 0; i < n; i++ )
      printf("%i ", a[i] );
   printf("\n");
}

static int intcomp( int a, int b )
{  if( a > b ) return  1;
   if( a < b ) return -1;
               return  0;
}

static int comp( const void * data, int i, int j, void * extra )
{  return intcomp( ( (int*)data )[i], ( (int*)data )[j] );  }

/* comparison for qsort: */
static int qscomp(const void * a, const void * b)
{  return intcomp( *(int*)a, *(int*)b );  }

static void swap( void * data, int i, int j )
{  int buf;
   buf = ( (int*)data )[i];
   ( (int*)data )[i] = ( (int*)data )[j];
   ( (int*)data )[j] = buf;
}

#define TESTLEN 5000
/* performance test with a random array: */
static void test()
{  int     a[TESTLEN], c[TESTLEN];
   int     i, j;
   clock_t start, total;

   total = 0;
   for( i = 0; i < 1000; i++ )
   {  for( j = 0; j < TESTLEN; j++ )
      {  a[j] = rand() % 5;
         c[j] = a[j];
      }
      start = clock();
      /*qsort( a, testlen, sizeof(int), &qscomp );*/
      sort( a, TESTLEN, &comp, &swap, NULL );
      total += clock() - start;  
      for( j = 0; j < TESTLEN-1; j++ )
      {  if( a[j] > a[j+1] )
         {  print( c, TESTLEN );
            print( a, TESTLEN );
            return;
         }
      }
   }
   printf("Time: %f\n", (float)total / CLOCKS_PER_SEC );
}

/* test with a small hard-coded array: */
#define TMLEN 3
static void testman( void )
{  int ta[TMLEN] = {3,2,1};
   print( ta, TMLEN );
   sort ( ta, TMLEN, &comp, &swap, NULL );
   print( ta, TMLEN );
}

int main( int argc, char** argv )
{  /*testman();
   return 0;*/

   test();
   return 0;
}

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

#143490

From	Robert Wessel <robertwessel2@yahoo.com>
Date	2019-04-27 08:30 -0500
Message-ID	<pvk8cedubu1tmovs4vhndi1k5nmc2oqjtv@4ax.com>
In reply to	#143484

On Sat, 27 Apr 2019 14:47:33 +0300, Anton Shepelev
<anton.txt@gmail.com> wrote:

>Here is a corrected version of my generic QuickSort implementation:
>
>---------------------------------- sort.h --------------------------------------
>
>/* ----------------------- A generic sorting routine ------------------------ */
>/* Comparison function:
>    > 0 <=> data[i] > data[j]
>    < 0 <=> data[i] < data[j]
>   == 0 <=> data[i] = data[j] */
>typedef int  (*comp_f)( const void * data, int i, int j, void * extra );
>
>/* Exchange ith and jth elements: */
>typedef void (*swap_f)( void * data, int i, int j );
>
>void sort
>(  void * data, /* pointer to data to sort         */
>   int    len,  /* length of data to sort          */
>   comp_f comp, /* comparison function             */
>   swap_f swap, /* swap function                   */
>   void * extra /* user-supplied parameter to comp */
>);
>
>---------------------------------- sort.c --------------------------------------
>#include <stdio.h>
>#include <limits.h>
>#include "sort.h"
>
>/* Partition an array [l..r] around a "pivot" member so that */
>/* the elements of the left sub-array do not exceed, and the ones */
>/* of the right sub-array are not less than, the pivot. */
>static int /* returns the right boundary of the left sub-array */
>partition
>(  void * data, /* pointer to the full array              */
>   int    l,    /* left  boundary of the sub-array        */
>   int    r,    /* right boundary of the sub-array, l < r */
>   comp_f comp,
>   swap_f swap,
>   void * extra
>)
>{  int p; /* index of the pivot, element */
>   p = ( l + r ) / 2; /* Chose the middle element as pivot */
>
>   while( 1 )
>   {  /* advance cursors until they stop at a pair of elements */
>      /* that should be swapped or meet or go past each other.  */
>      /* The pivot element serves as a sentinel.                */
>      while( comp( data, l, p, extra ) < 0 ) l += 1;
>      while( comp( data, r, p, extra ) > 0 ) r -= 1;
>      if( l >= r ) break;
>
>      swap( data, l, r );      /* Swap the pair found         */
>           if( l == p ) p = r; /* Update pivot location if it */
>      else if( r == p ) p = l; /* was changed during the swap */
>
>      /* Advance the cursors. If they are adjecent they will cross: */
>      l += 1; r -= 1;
>   }
>   return r;
>}
>
>void sort
>(  void * data,
>   int    len,
>   comp_f comp,
>   swap_f swap,
>   void * extra
>)
>{  /* In this algorithm, minimun sufficient stack size is Log(len) */
>   int sl[sizeof(int) * CHAR_BIT]; /* left  sub-array boundaries on the stack */
>   int sr[sizeof(int) * CHAR_BIT]; /* right sub-array boundaries nn the stack */
>
>   int d;          /* stack depth */
>   int l, r;       /* left and right boundaries of a sub-array */
>   int lpos, rpos; /* positions of the left and right new sub-arrays on the stack */
>   int newr;       /* the right boundary of the new left sub-array */
>
>   d     = 1; /* Put the initial sub-array onto the stack */
>   sl[0] = 0; sr[0] = len - 1;   
>   while( d > 0 )
>   {  d -= 1; /* Take an element from the stack */
>      l = sl[d]; r = sr[d];
>      if( l >= r ) continue; /* Skip a subarray shorter than two */
>      
>      newr = partition( data, l , r, comp, swap, extra );
>
>      /* process the shorter sub-array first to ease the stack: */
>      lpos = d; rpos = d; 
>      if( newr - l > r - newr - 1 ) rpos += 1;
>      else                          lpos += 1;
>
>      /* Put partiioned sub-arrays onto the stack: */
>      sl[lpos] = l;        sr[lpos] = newr;
>      sl[rpos] = newr + 1; sr[rpos] = r;
>      d += 2;
>   }
>}
>
>---------------------------------- test.c --------------------------------------
>
>#include <stdio.h>
>#include <stdlib.h>
>#include <time.h>
>#include "sort.h"
>
>static void print( int * a, int n )
>{  int i;
>   for( i = 0; i < n; i++ )
>      printf("%i ", a[i] );
>   printf("\n");
>}
>
>static int intcomp( int a, int b )
>{  if( a > b ) return  1;
>   if( a < b ) return -1;
>               return  0;
>}
>
>static int comp( const void * data, int i, int j, void * extra )
>{  return intcomp( ( (int*)data )[i], ( (int*)data )[j] );  }
>
>/* comparison for qsort: */
>static int qscomp(const void * a, const void * b)
>{  return intcomp( *(int*)a, *(int*)b );  }
>
>static void swap( void * data, int i, int j )
>{  int buf;
>   buf = ( (int*)data )[i];
>   ( (int*)data )[i] = ( (int*)data )[j];
>   ( (int*)data )[j] = buf;
>}
>
>#define TESTLEN 5000
>/* performance test with a random array: */
>static void test()
>{  int     a[TESTLEN], c[TESTLEN];
>   int     i, j;
>   clock_t start, total;
>
>   total = 0;
>   for( i = 0; i < 1000; i++ )
>   {  for( j = 0; j < TESTLEN; j++ )
>      {  a[j] = rand() % 5;
>         c[j] = a[j];
>      }
>      start = clock();
>      /*qsort( a, testlen, sizeof(int), &qscomp );*/
>      sort( a, TESTLEN, &comp, &swap, NULL );
>      total += clock() - start;  
>      for( j = 0; j < TESTLEN-1; j++ )
>      {  if( a[j] > a[j+1] )
>         {  print( c, TESTLEN );
>            print( a, TESTLEN );
>            return;
>         }
>      }
>   }
>   printf("Time: %f\n", (float)total / CLOCKS_PER_SEC );
>}
>
>/* test with a small hard-coded array: */
>#define TMLEN 3
>static void testman( void )
>{  int ta[TMLEN] = {3,2,1};
>   print( ta, TMLEN );
>   sort ( ta, TMLEN, &comp, &swap, NULL );
>   print( ta, TMLEN );
>}
>
>int main( int argc, char** argv )
>{  /*testman();
>   return 0;*/
>
>   test();
>   return 0;
>}


I may have lost track, but is this intended to be a generally usable
implementation at the end of the day, or a demonstration of letting
the compiler properly specialize a sort implementation?

If the former, I'd offer a few suggestions on the Quicksort
implementation.

First, just swap the pivot to the first location (or last) in the
partition after picking it, and adjust the edge of the subarray you're
partitioning.  That way you don't have to keep checking if you've
moved it.

The usual Quicksort optimizations, median-of-three for pivot
selection, insertion sorting small partitions (you have a choice of a
single insertion sort pass over the entire input, or insertion sorts
of the individual small partitions - given cache effects, the latter
is usually recommended today), are worthwhile optimizations, with
minimal complexity.  You've already dealt with the stack issue
(although I personally prefer the semi-recursive form, it's not a big
difference).

Introsort is a significant upgrade to basic Quicksort, and bounds
performance to O(n log n).  The basic idea is to keep an eye on the
efficiency of the partitioning process, and switch to Heapsort if it's
performing poorly.  More or less you look at the size of the partition
relative to it depth - after (depth) three partitioning operations,
partitions should be about an eighth the size of the input - if you
are showing considerably larger than that, give up and Heapsort the
partition instead.  It does add significant complexity - the Heapsort
implementation will be about as big as the rest of the (optimized)
Quicksort.

Musser's original Introsort paper is rather interesting reading, not
so much for the algorithm (which is one of those obvious-in-hind-sight
things), but for his discussion of just how easy it is to generate
pathological inputs for Quicksort.  And given that this is 2019, you
pretty much have to assume that inputs will be constructed in an
actively malicious manner, unless you can specifically prove
otherwise.

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

#143567

From	Anton Shepelev <anton.txt@gmail.com>
Date	2019-05-02 14:52 +0300
Message-ID	<20190502145240.03216d54fb7c1449b1f2fff7@gmail.com>
In reply to	#143490

Robert Wessel:

> I may have lost track, but is this intended to be a
> generally usable implementation at the end of the day, or
> a demonstration of letting the compiler properly
> specialize a sort implementation?

It is generally usable for my purposes because pathological
cases are improbable.  It is not the compiler, but the
programmer that specialises an implementation.  How can a
compiler do it?

> If the former, I'd offer a few suggestions on the
> Quicksort implementation.
>
> First, just swap the pivot to the first location (or last)
> in the partition after picking it, and adjust the edge of
> the subarray you're partitioning.  That way you don't have
> to keep checking if you've moved it.

Then the pivot will no loger work as sentinel and I shall
have to use a complex stop condition in:

   while( comp( data, l, p, extra ) < 0 ) l += 1;
   while( comp( data, r, p, extra ) > 0 ) r -= 1;

> The usual Quicksort optimizations, median-of-three for
> pivot selection, insertion sorting small partitions (you
> have a choice of a single insertion sort pass over the
> entire input, or insertion sorts of the individual small
> partitions - given cache effects, the latter is usually
> recommended today), are worthwhile optimizations, with
> minimal complexity.

Agreed.

I have tried switching to insertion sort when the subarray
becomes shorter than a specified legth, but found little
benefit on random arrays with TCC for some reason.  Notice
that insertion sort using swaps is by a constant factor
slower than the more optimal but non-generic implementation.

> You've already dealt with the stack issue (although I
> personally prefer the semi-recursive form, it's not a big
> difference).

You mean reliance of tail-call optimisation?  I dislike it
for readability.  Recursive code is compiled into iterative
machine code.  This is misleading.

> Introsort is a significant upgrade to basic Quicksort, and
> bounds performance to O(n log n).  The basic idea is to
> keep an eye on the efficiency of the partitioning process,
> and switch to Heapsort if it's performing poorly.  More or
> less you look at the size of the partition relative to it
> depth - after (depth) three partitioning operations,
> partitions should be about an eighth the size of the input
> - if you are showing considerably larger than that, give
> up and Heapsort the partition instead.  It does add
> significant complexity - the Heapsort implementation will
> be about as big as the rest of the (optimized) Quicksort.

In that case, I think, using Heapsort all through is
simpler.  I should refer to avoid a compound sorting
algorithm, be it QuickSort + Insertion sort or QuickSort +
HeapSort.

> Musser's original Introsort paper is rather interesting
> reading, not so much for the algorithm (which is one of
> those obvious-in-hind-sight things), but for his
> discussion of just how easy it is to generate pathological
> inputs for Quicksort.  And given that this is 2019, you
> pretty much have to assume that inputs will be constructed
> in an actively malicious manner, unless you can
> specifically prove otherwise.

A simple solution would be to select a random pivot.

-- 
()  ascii ribbon campaign -- against html e-mail
/\  http://preview.tinyurl.com/qcy6mjc [archived]

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

Page 3 of 6 — ← Prev page 1 2 [3] 4 5 6 Next page →

csiph-web

qsort() standard functions

Contents

#143443

#143442

#143448

#143453

#143458

#143467

#143485

#143492

#143494

#143572

#143574

#143576

#143606

#143592

#143602

#143569

#143571

#143484

#143490

#143567