Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #143484
| From | Anton Shepelev <anton.txt@gmail.com> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: qsort() standard functions |
| Date | 2019-04-27 14:47 +0300 |
| Organization | A noiseless patient Spider |
| Message-ID | <20190427144733.63852ec695135de51c951373@gmail.com> (permalink) |
| References | (10 earlier) <9eb64b53-05ac-4eb5-8a48-053341616af3@googlegroups.com> <ae3d83e3-0647-4474-b496-2b77da35d46d@googlegroups.com> <cfd3e5ea-bfd3-4e46-96e5-4785d017764a@googlegroups.com> <20190425234955.d5e41956e47d87a13c5d2be8@gmail.com> <87ef5pu5cf.fsf@bsb.me.uk> |
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;
}
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