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

Groups > comp.lang.c > #143567

Re: qsort() standard functions

Show all headers | View raw

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]

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

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

csiph-web