Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #143408
| From | Anton Shepelev <anton.txt@gmail.com> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: qsort() standard functions |
| Date | 2019-04-25 00:22 +0300 |
| Organization | A noiseless patient Spider |
| Message-ID | <20190425002215.1c2496a880790d835596fc4e@gmail.com> (permalink) |
| References | (2 earlier) <fda6fac4-7cdb-4c35-9383-9c65a154a70f@googlegroups.com> <q9qcpl$hs6$2@news.xmission.com> <b648a32d-5671-4702-9b6d-5ecba83f3559@googlegroups.com> <19389b6d-4521-467c-8308-8fc152e94e1b@googlegroups.com> <e81a78e6-05ff-442e-b037-8005bf2fe0a1@googlegroups.com> |
fir:
> if someone is boring instead of reading and answering dik
> (even reading is harmfull) state some usefull thread, i
> dont know it might be
>
> "how to write a quicksort in non stack version"
Good idea. Here is my quick take at it:
------------------------------------ sort.h ------------------------------------
/* Comparison function:
> 0 <=> data[i] > data[j]
< 0 <=> data[i] < data[j]
== 0 <=> data[i] = data[j] */
typedef int (*comp_f)( void * data, int i, int j, const void * extra );
typedef void (*swap_f)( void * data, int i, int j );
void sort /* sort an array */
( void * data, /* pointer to the array to be sorted */
int len, /* length of that array */
comp_f comp, /* comparison function */
swap_f swap, /* swap function */
const void * extra /* user-suppied data to comp */
);
------------------------------------ sort.c ------------------------------------
#include <stdio.h>
#include <limits.h>
#include "sort.h"
static int partition
( void * data,
int l,
int r,
comp_f comp,
swap_f swap,
const void * extra
)
{ int m;
m = (l + r)/2;
while( 1 )
{ while( comp(data, l, m, extra) < 0 ) l = l + 1;
while( comp(data, r, m, extra) > 0 ) r = r - 1;
if( l >= r ) break;
swap( data, l, r );
if( l == m ) m = r;
else if( r == m ) m = l;
l = l + 1; r = r - 1;
}
return r;
}
void sort
( void * data,
int len,
comp_f comp,
swap_f swap,
const void * extra
)
{ int sl[sizeof(int) * CHAR_BIT];
int sr[sizeof(int) * CHAR_BIT];
int newr, q, l, r, lpos, rpos;
q = 1;
l = 0; r = len - 1;
sl[0] = l; sr[0] = r;
while( q > 0 )
{ q = q - 1;
l = sl[q]; r = sr[q];
if( l >= r ) continue;
newr = partition( data, l , r, comp, swap, extra );
/* process the shorter sub-array first to ease the stack: */
lpos = q; rpos = q;
if( newr - l > r - newr - 1 ) rpos = rpos + 1;
else lpos = lpos + 1;
sl[lpos] = l; sr[lpos] = newr;
sl[rpos] = newr+1; sr[rpos] = r;
q = q + 2;
}
}
--
() 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
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