11
\$\begingroup\$

[Latest update: benchmark program and preliminary resuls available, see below]

So I want to test the speed/complexity tradeoff with a classic application: sorting.

Write an ANSI C function that sorts an array of floating point numbers in increasing order.

You can't use any libraries, system calls, multithreading or inline ASM.

Entries judged on two components: code length and performance. Scoring as follows: entries will be sorted by length (log of #characters without whitespace, so you can keep some formatting) and by performance (log of #seconds over a benchmark), and each interval [best,worst] linearly normalised to [0,1]. The total score of a program will be the average of the two normalised scores. Lowest score wins. One entry per user.

Sorting will have to (eventually) be in place (i.e. the input array will have to contain sorted values at return time), and you must use the following signature, including names:

void sort(float* v, int n) {

}

Characters to be counted: those in the sort function, signature included, plus additional functions called by it (but not including testing code).

The program must handle any numeric value of float and arrays of length >=0, up to 2^20.

I'll plug sort and its dependencies into a testing program and compile on GCC (no fancy options). I'll feed a bunch of arrays into it, verify correctness of results and total run time. Tests will be run on an Intel Core i7 740QM (Clarksfield) under Ubuntu 13.
Array lengths will span the whole allowed range, with a higher density of short arrays. Values will be random, with a fat-tail distribution (both in the positive and negative ranges). Duplicated elements will be included in some tests.
The test program is available here: https://gist.github.com/anonymous/82386fa028f6534af263
It imports the submission as user.c. The number of test cases (TEST_COUNT) in the actual benchmark will be 3000. Please provide any feedback in the question comments.

Deadline: 3 weeks (7 April 2014, 16:00 GMT). I will post the benchmark in 2 weeks.
It may be advisable to post close to the deadline to avoid giving away your code to competitors.

Preliminary results, as of benchmark publication:
Here are some results. The last column shows the score as a percentage, the higher the better, putting Johnny Cage in first place. Algorithms that were orders of magnitude slower than the rest were run on a subset of tests, and time extrapolated. C's own qsort is included for comparison (Johnny's is faster!). I'll perform a final comparison at closing time.

enter image description here

\$\endgroup\$
  • 3
    \$\begingroup\$ Can you provide the benchmark? Different sorting functions perform differently based on the nature of the data. E.g. bubble sort is faster than the stdlib quicksort for tiny arrays. We might like to optimize for your benchmark. \$\endgroup\$ – Claudiu Mar 14 '14 at 17:20
  • \$\begingroup\$ @Claudiu I once saw a lovely short version of quicksort, that ran just as well as any other on data where every element was different. But if some elements were the same, it ran at an absolute snail's pace. I'm not talking about the known issue of bad choice of pivot in sorted / partially sorted arrays. My test data was completely randomly shuffled. This particular version just didn't like duplicates. Weird, but true. \$\endgroup\$ – Level River St Mar 14 '14 at 17:37
  • 3
    \$\begingroup\$ Welcome to PPCG! While we don't prohibit language-specific challenges, we do strongly encourage formulating questions in a language-agnostic manner whenever possible. Consider it for your next question, and have fun with this one! \$\endgroup\$ – Jonathan Van Matre Mar 14 '14 at 17:55
  • 1
    \$\begingroup\$ @steveverrill: I don't follow. It doesn't matter what your unit is because you scale it from 0 to 1 anyway. If min is 1 hour and max is 3 hours, something that takes 1.5 hours will be 0.25 regardless of whether min is 60 minutes, max is 180 minutes, and it takes 90 minutes \$\endgroup\$ – Claudiu Mar 14 '14 at 19:13
  • 1
    \$\begingroup\$ OP only said no inline assembly - he didn't say anything about intrinsics. \$\endgroup\$ – Paul R Mar 16 '14 at 9:11

14 Answers 14

6
\$\begingroup\$

150 character

Quicksort.

/* 146 character.
 * sizeup 1.000; speedup 1.000; */
#define REC_SIZE    \
    sort(l, v+n-l); \
    n = l-v;

/* 150 character.
 * sizeup 1.027; speedup 1.038; */
#define REC_FAST  \
    sort(v, l-v); \
    n = v+n-l;    \
    v = l;

void sort(float* v, int n)
{
    while ( n > 1 )
     {
       float* l = v-1, * r = v+n, x = v[n/2], t;
L:
       while ( *++l < x );
       while ( x < (t = *--r) );

       if (l < r)
        {
          *r = *l; *l = t;
          goto L;
        }
       REC_FAST
     }
}

Compressed.

void sort(float* v, int n) {
while(n>1){float*l=v-1,*r=v+n,x=v[n/2],t;L:while(*++l<x);while(x<(t=*--r));if(l<r){*r=*l;*l=t;goto L;}sort(v,l-v);n=v+n-l;v=l;}
}
\$\endgroup\$
  • \$\begingroup\$ Leading the race! \$\endgroup\$ – Mau Mar 31 '14 at 9:49
3
\$\begingroup\$

150 chars (without whitespaces)

void sort(float *v, int n) {
    int l=0;
    float t, *w=v, *z=v+(n-1)/2;

    if (n>0) {
      t=*v; *v=*z; *z=t;
      for(;++w<v+n;)
        if(*w<*v)
        {
          t=v[++l]; v[l]=*w; *w=t;
        }
      t=*v; *v=v[l]; v[l]=t;
      sort(v, l++);
      sort(v+l, n-l);
    }
}
\$\endgroup\$
  • \$\begingroup\$ Awesome, first entry! \$\endgroup\$ – Mau Mar 15 '14 at 15:39
  • \$\begingroup\$ Feel free to post an answer with SSE and I'll list it in the scoreboard, though I'm interested in 'portable' solutions for the challenge. \$\endgroup\$ – Mau Mar 15 '14 at 21:10
  • \$\begingroup\$ if(*w<*v) { t=v[++l]; v[l]=*w; *w=t; } can be if(*w<*v) t=v[++l], v[l]=*w, *w=t; \$\endgroup\$ – ASKASK Mar 17 '14 at 1:43
3
\$\begingroup\$

67 70 69 chars

Not fast at all, but incredibly small. It's a hybrid between a selection sort and bubble sort algorithm I guess. If you are actually trying to read this, then you should know that ++i-v-n is the same as ++i != v+n .

void sort(float*v,int n){
    while(n--){
        float*i=v-1,t;
        while(++i-v-n)
            *i>v[n]?t=*i,*i=v[n],v[n]=t:0;
    }
}
\$\endgroup\$
  • \$\begingroup\$ if(a)b -> a?b:0 saves a char. \$\endgroup\$ – ugoren Mar 27 '14 at 20:16
  • \$\begingroup\$ Well, ++i-v-n is the same as ++i != v+n only in a conditional, of course. \$\endgroup\$ – wchargin Mar 27 '14 at 23:25
  • \$\begingroup\$ @ugoren i think you posted that comment on the wrong answer \$\endgroup\$ – ASKASK Mar 28 '14 at 1:06
  • \$\begingroup\$ @ASKASK, if(*i>v[n])... -> *i>v[n]?...:0 \$\endgroup\$ – ugoren Mar 29 '14 at 12:52
  • \$\begingroup\$ are you sure that is how the prescedence works? \$\endgroup\$ – ASKASK Mar 29 '14 at 18:36
2
\$\begingroup\$

123 chars (+3 newlines)

A standard Shell sort, compressed.

d,i,j;float t;
void sort(float*v,int n){
for(d=1<<20;i=d/=2;)for(;i<n;v[j]=t)for(t=v[j=i++];j>=d&&v[j-d]>t;j-=d)v[j]=v[j-d];
}  

PS: discovered it is still 10x slower than quicksort. You might as well ignore this entry.

\$\endgroup\$
  • \$\begingroup\$ Your choice of gaps could be better. Thats probably why this is a lot slower than quicksort. en.wikipedia.org/wiki/Shellsort#Gap_sequences \$\endgroup\$ – FDinoff Mar 16 '14 at 17:18
  • \$\begingroup\$ I was amazed to discover how much the gap sequence affects the speed. With a good sequence it comes close to quicksort but remains slower in my experience. \$\endgroup\$ – Florian F Mar 19 '14 at 9:55
  • \$\begingroup\$ Don't be too hard on yourself. You're in third place. \$\endgroup\$ – Kevin - Reinstate Monica Apr 3 '14 at 20:27
2
\$\begingroup\$

395 character

Mergesort.

void sort(float* v,int n){static float t[16384];float*l,*r,*p,*q,*a=v,*b=v+n/2,
*c=v+n,x;if(n>1){sort(v,n/2);sort(v+n/2,n-n/2);while(a!=b&&b!=c)if(b-a<=c-b&&b-
a<=16384){for(p=t,q=a;q!=b;)*p++=*q++;for(p=t,q=t+(b-a);p!=q&&b!=c;)*a++=(*p<=
*b)?*p++:*b++;while(p!=q)*a++=*p++;}else{for(l=a,r=b,p=t,q=t+16384;l!=b&&r!=c&&
p!=q;)*p++=(*l<=*r)?*l++:*r++;for(q=b,b=r;l!=q;)*--r=*--q;for(q=t;p!=q;)*a++=
*q++;}}}

Formatted.

static float* copy(const float* a, const float* b, float* out)
{   while ( a != b ) *out++ = *a++; return out;
}
static float* copy_backward(const float* a, const float* b, float* out)
{   while ( a != b ) *--out = *--b; return out;
}

static void ip_merge(float* a, float* b, float* c)
{
    /* 64K (the more memory, the better this performs). */
#define BSIZE (1024*64/sizeof(float))
    static float t[BSIZE];

    while ( a != b && b != c )
     {
       int n1 = b - a;
       int n2 = c - b;

       if (n1 <= n2 && n1 <= BSIZE)
        {
          float* p = t, * q = t + n1;
          /* copy [a,b] sequence. */
          copy(a, b, t);
          /* merge. */
          while ( p != q && b != c )
             *a++ = (*p <= *b) ? *p++ : *b++;
          /* copy remaining. */
          a = copy(p, q, a);
        }
       /* backward merge omitted. */
       else
        {
          /* there are slicker ways to do this; all require more support
           * code. */
          float* l = a, * r = b, * p = t, * q = t + BSIZE;
          /* merge until sequence end or buffer end is reached. */
          while ( l != b  && r != c && p != q )
             *p++ = (*l <= *r) ? *l++ : *r++;
          /* compact remaining. */
          copy_backward(l, b, r);
          /* copy buffer. */
          a = copy(t, p, a);
          b = r;
        }
     }
}

void sort(float* v, int n)
{
    if (n > 1)
     {
       int h = n/2;
       sort(v, h); sort(v+h, n-h); ip_merge(v, v+h, v+n);
     }
}
\$\endgroup\$
2
\$\begingroup\$

331 326 327 312 chars

Does radix sort 8 bits at a time. Uses a fancy bithack to get negative floats to sort correctly (stolen from http://stereopsis.com/radix.html). It's not that compact, but it is really fast (~8x faster than the fastest prelim entry). I'm hoping for speed trumping code size...

#define I for(i=n-1;i>=0;i--)
#define J for(i=0;i<256;i++)
#define R for(r=0;r<4;r++)
#define F(p,q,k) I p[--c[k][q[i]>>8*k&255]]=q[i]

void sort(float *a, int n) {
  int *A = a,i,r,x,c[4][257],B[1<<20];
  R J c[r][i]=0;
  I {
    x=A[i]^=A[i]>>31|1<<31;
    R c[r][x>>8*r&255]++;
  }
  J R c[r][i+1]+=c[r][i];

  F(B,A,0);
  F(A,B,1);
  F(B,A,2);
  F(A,B,3)^(~B[i]>>31|1<<31);
}
\$\endgroup\$
2
\$\begingroup\$

511 424 character

Inplace radixsort

Update: Switches to insertion sort for smaller array sizes (increases benchmark performance by a factor of 4.0).

#define H p[(x^(x>>31|1<<31))>>s&255]
#define L(m) for(i=0;i<m;i++)
void R(int*a,int n,int s){if(n<64){float*i,*j,x;for(i=a+1;i<a+n;i++){x=*i;for(
j=i;a<j&&x<j[-1];j--)*j=j[-1];*j=x;}}else{int p[513]={},*q=p+257,z=255,i,j,x,t
;L(n)x=a[i],H++;L(256)p[i+1]+=q[i]=p[i];for(z=255;(i=p[z]-1)>=0;){x=a[i];while
((j=--H)!=i)t=x,x=a[j],a[j]=t;a[i]=x;while(q[z-1]==p[z])z--;}if(s)L(256)R(a+p[
i],q[i]-p[i],s-8);}}void sort(float* v,int n){R(v,n,24);}

Formatted.

/* XXX, BITS is a power of two. */
#define BITS 8
#define BINS (1U << BITS)
#define TINY 64

#define SWAP(type, a, b) \
    do { type t=(a);(a)=(b);(b)=t; } while (0)

static inline unsigned int floatbit_to_sortable_(const unsigned int x)
{   return x ^ ((0 - (x >> 31)) | 0x80000000);
}

static inline unsigned int sortable_to_floatbit_(const unsigned int x)
{   return x ^ (((x >> 31) - 1) | 0x80000000);
}

static void insertsort_(unsigned int* a, unsigned int* last)
{
    unsigned int* i;
    for ( i = a+1; i < last; i++ )
     {
       unsigned int* j, x = *i;
       for ( j = i; a < j && x < *(j-1); j-- )
          *j = *(j-1);
       *j = x;
     }
}

static void radixsort_lower_(unsigned int* a, const unsigned int size,
  const unsigned int shift)
{
    /* @note setup cost can be prohibitive for smaller arrays, switch to
     * something that performs better in these cases. */
    if (size < TINY)
     {
       insertsort_(a, a+size);
       return;
     }

    unsigned int h0[BINS*2+1] = {}, * h1 = h0+BINS+1;
    unsigned int i, next;

    /* generate histogram. */
    for ( i = 0; i < size; i++ )
       h0[(a[i] >> shift) % BINS]++;

    /* unsigned distribution.
     * @note h0[BINS] == h1[-1] == @p size; sentinal for bin advance. */
    for ( i = 0; i < BINS; i++ )
       h0[i+1] += (h1[i] = h0[i]);

    next = BINS-1;
    while ( (i = h0[next]-1) != (unsigned int) -1 )
     {
       unsigned int x = a[i];
       unsigned int j;
       while ( (j = --h0[(x >> shift) % BINS]) != i )
          SWAP(unsigned int, x, a[j]);
       a[i] = x;
       /* advance bins.
        * @note skip full bins (zero sized bins are full by default). */
       while ( h1[(int) next-1] == h0[next] )
          next--;
     }

    /* @note bins are sorted relative to one another at this point but
     * are not sorted internally. recurse on each bin using successive
     * radii as ordering criteria. */
    if (shift != 0)
       for ( i = 0; i < BINS; i++ )
          radixsort_lower_(a + h0[i], h1[i] - h0[i], shift-BITS);
}

void sort(float* v, int n)
{
    unsigned int* a = (unsigned int*) v;
    int i;

    for ( i = 0; i < n; i++ )
       a[i] = floatbit_to_sortable_(a[i]);

    radixsort_lower_(a, n, sizeof(int)*8-BITS);

    for ( i = 0; i < n; i++ )
       a[i] = sortable_to_floatbit_(a[i]);
}
\$\endgroup\$
  • \$\begingroup\$ Nice! Try flagging the original answer. \$\endgroup\$ – Mau Mar 31 '14 at 16:48
  • \$\begingroup\$ @Mau: Thanks and will do. Wanted to mention an error in the benchmarking code. The cast to void* in qsort (line 88) is throwing off the pointer arithmetic. \$\endgroup\$ – MojoJojoBojoHojo Mar 31 '14 at 16:57
1
\$\begingroup\$

121 114 111 characters

Just a quick-and-dirty bubblesort, with recursion. Probably not very efficient.

void sort(float*v,int n){int i=1;float t;for(;i<n;i++)v[i-1]>(t=v[i])&&(v[i]=v[i-1],v[i-1]=t);n--?sort(v,n):0;}

Or, the long version

void sort(float* values, int n) {
  int i=1;  // Start at 1, because we check v[i] vs v[i-1]
  float temp;
  for(; i < n; i++) {
    // If v[i-1] > v[i] is true (!= 0), then swap.
    // Note I am assigning values[i] to temp here. Below I want to use commas
    // so the whole thing fits into one statement, but if you assign temp there you will get sequencing issues (i.e unpredictable swap results)
    values[i - 1] > (temp = values[i]) && (
    // I tried the x=x+y,y=x-y,x=x-y trick, but using a temp
    // turns out to be shorter even if we have to declare the t variable.
      values[i] = values[i - 1], 
      values[i - 1] = temp);
  }

  // If n == 1, we are done. Otherwise, sort the first n - 1 elements recursively. 
  // The 0 is just because the third statement cannot be empty.
  n-- ? sort(values, n) : 0;
}
\$\endgroup\$
  • \$\begingroup\$ As an aside, I found a really interesting algorithm here: rosettacode.org/wiki/Sorting_algorithms/Pancake_sort#C But I cannot get it compressed enough to beat 114 :) \$\endgroup\$ – CompuChip Mar 17 '14 at 18:58
  • \$\begingroup\$ your program seems to fail to complete in some cases and write out of bounds in other cases. \$\endgroup\$ – Mau Mar 29 '14 at 22:46
  • \$\begingroup\$ @Mau I tested it on some inputs manually and seemed to work ok, but due to lack of time I didn't test it very thouroughly so I am sure that there is some bad behavior somewhere. Could you post a test case where you ran into trouble please? \$\endgroup\$ – CompuChip Mar 30 '14 at 16:10
  • \$\begingroup\$ test program available above :) \$\endgroup\$ – Mau Mar 30 '14 at 16:26
  • \$\begingroup\$ Hmm I tried running it, I am getting some ` munmap_chunk(): invalid pointer` errors in the cleanup part, but nothing about the test failing. However you are right that there is an off-by-one error, and I seem to have some sequencing issues (the comma-separated list of statements does not do what I expect it to). I'll try to fix it. \$\endgroup\$ – CompuChip Mar 30 '14 at 19:47
1
\$\begingroup\$

221 193 172 characters

Heapsort - Not the smallest, but in-place and guarantees O(n*log(n)) behavior.

static void sink(float* a, int i, int n, float t)
{
    float* b = a+i;

    for ( ; (i = i*2+2) <= n; b = a+i )
     {
       i -= (i == n || a[i] < a[i-1]) ? 1 : 0;

       if (t < a[i])
          *b = a[i];
       else
          break;
     }
    *b = t;
}

void sort(float* a, int n)
{
    int i;
    /* make. */
    for ( i = n/2-1; i >= 0; i-- )
       sink(a, i, n, a[i]);
    /* sort. */
    for ( i = n-1; i > 0; i-- )
     {
       float t = a[i]; a[i] = a[0];
       sink(a, 0, i, t);
     }
}

Compressed.

void sort(float* a,int n){
#define F(p,q,r,x,y) for(i=n/p;q>0;){t=a[i];r;for(j=x;(b=a+j,j=j*2+2)<=y&&(j-=(j==y||a[j]<a[j-1]),t<a[j]);*b=a[j]);*b=t;}
float*b,t;int i,j;F(2,i--,,i,n)F(1,--i,a[i]=*a,0,i)
}
\$\endgroup\$
  • \$\begingroup\$ You can save some characters by deducting the whitespace. And possibly also the mandatory function signature, but since there are some entries that counted that I've asked questioner to clarify whether it should be counted. \$\endgroup\$ – Jonathan Van Matre Mar 19 '14 at 11:53
  • \$\begingroup\$ @user19425: If you run the test program with TEST_COUNT = 3000, it seems to fail at least one test. \$\endgroup\$ – Mau Mar 30 '14 at 19:50
1
\$\begingroup\$

154 166 characters

OK, here is a longer but faster quicksort.

void sort(float*v,int n){while(n>1){float*j=v,*k=v+n-1,t=*j;while(j<k){while(j<k&&*k>=t)k--;*j=*k;while(j<k&&*j<t)j++;*k=*j;}*k++=t;sort(k,v+n-k);n=j-v;}}

Here is a correction to survive sorted inputs. And formatted since white space doesn't count.

void sort(float*v, int n){
    while(n>1){
        float*j=v, *k=j+n/2, t=*k;
        *k = *j;
        k = v+n-1;
        while(j<k){
            while(j<k && *k>=t) k--;
            *j=*k;
            while(j<k && *j<t) j++;
            *k=*j;
        }
        *k++ = t;
        sort(k,v+n-k);
        n = j-v;
    }
}
\$\endgroup\$
  • \$\begingroup\$ This version seems to write out of bounds in some cases, not terminating in others. \$\endgroup\$ – Mau Mar 31 '14 at 6:48
  • \$\begingroup\$ PS: OK, it is very slow on a sorted set. But the problem statement says the input is random. \$\endgroup\$ – Florian F Apr 2 '14 at 20:53
  • \$\begingroup\$ The values are random. I never said anything about what order they'd be in :-) But yes, there are chunks covering about 10% of all values sorted in ascending order and another 10% in descending order. \$\endgroup\$ – Mau Apr 3 '14 at 10:37
  • 1
    \$\begingroup\$ Fair enough. And a sort() should work on sorted input. I'll update my submission, then... \$\endgroup\$ – Florian F Apr 3 '14 at 20:02
1
\$\begingroup\$

150 character

Shellsort (w/Knuth gap).

void sort(float* v, int n) {
float*p,x;int i,h=0;while(2*(i=h*3+1)<=n)h=i;for(;h>0;h/=3)for(i=h;i<n;i++){x=v[i];for(p=v+i-h;p>=v&&x<*p;p-=h)p[h]=*p;p[h]=x;}
}

Formatted.

static void hsort(float* v, const int h, const int n)
{
    int i;
    for (i = h; i < n; i++) {
        float* p, x = v[i];
        for (p = v + i-h; p >= v && x < *p; p -= h)
            p[h] = *p;
        p[h] = x;
    }
}

void sort(float* v, int n)
{
    int i, h = 0;
    while (2*(i = h*3+1) <= n)
        h = i;
    for (; h > 0; h /= 3)
        hsort(v, h, n);
}
\$\endgroup\$
1
\$\begingroup\$

C 270 (golfed)

#define N 1048576
void sort(float*v,int n)
{
float f[N],g;
int m[N],i,j,k,x;
g=v[0];k=0;
for(i=0;i<n;i++){for(j=0;j<n;j++){if(m[j]==1)continue;if(v[j]<g){g=v[j];k=j;}}f[i]=g;m[k]=1;for(x=0;x<n;x++){if(m[x]==0){g=v[x];k=x;break;}}}
for(i=0;i<n;i++){v[i]=f[i];}
}

Explanation: A blank array is used to store each successive minimum number. An int array is a mask with 0 indicating the number has not yet been copied. After getting the minimum value a mask=1 skips already used numbers. Then the array is copied back to original.

I changed the code to eliminate use of library functions.

\$\endgroup\$
0
\$\begingroup\$

144

I shamelessly took Johnny's code, added a tiny optimization and compressed the code in a very dirty way. It should be shorter and faster.

Note that depending on your compiler, sort(q,v+n- ++q) must be replaced by sort(++q,v+n-q).

#define w ;while(
void sort(float*v, int n){
    w n>1){
        float *p=v-1, *q=v+n, x=v[n/2], t
        w p<q){
            w *++p<x )
            w *--q>x );
            if( p<q ) t=*p, *p=*q, *q=t;
        }
        sort(q,v+n- ++q);
        n = p-v;
    }
}

Well, actually, I started form my code and optimized it, but it seems Johnny already made all the right choices. So I ended up with quasi his code. I didn't think of the goto trick, but I could do without.

\$\endgroup\$
0
\$\begingroup\$

228 character

Radixsort.

void sort(float* v, int n) {
#define A(x,y,z) for(x=y;x<z;x++)
#define B h[(a[i]^(a[i]>>31|1<<31))>>j*8&255]
    int m[1<<20],*a=v,*b=m,*t,i,j;
    A(j,0,4) {
        int h[256] = {};
        A(i,0,n) B++;
        A(i,1,256) h[i] += h[i-1];
        for (i = n-1; i >= 0; i--)
            b[--B] = a[i];
        t = a, a = b, b = t;
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.