[ Последнее обновление: эталонная программа и предварительные результаты доступны, см. Ниже]

Поэтому я хочу проверить компромисс между скоростью и сложностью с классическим приложением: сортировка.

Напишите функцию ANSI C, которая сортирует массив чисел с плавающей точкой в порядке возрастания .

Вы не можете использовать любые библиотеки, системные вызовы, многопоточность или встроенный ASM.

Записи оцениваются по двум компонентам: длина кода и производительность. Оценки следующим образом: записи будут отсортированы по длине (журнал #characters без пробелов, так что вы можете сохранить некоторое форматирование) и производительности (журнал #seconds за тест), и каждый интервал [лучший, худший] линейно нормализуется до [ 0,1]. Общий балл программы будет средним из двух нормализованных баллов. Самый низкий балл побеждает. Одна запись на пользователя.

Сортировка должна (в конечном итоге) быть на месте (т. Е. Входной массив должен содержать отсортированные значения во время возврата), и вы должны использовать следующую подпись, включая имена:

void sort(float* v, int n) {

}

Подсчитываемые символы: символы в sortфункции, включая подпись, плюс дополнительные функции, вызываемые ею (но не включая код тестирования).

Программа должна обрабатывать любые числовые значения floatи массивы длиной> = 0, вплоть до 2 ^ 20.

Я подключу sortи его зависимости к тестирующей программе и скомпилирую на GCC (никаких изящных опций). Я добавлю в него кучу массивов, проверим правильность результатов и общее время выполнения. Тесты будут проводиться на Intel Core i7 740QM (Clarksfield) под Ubuntu 13.
Длины массивов будут охватывать весь допустимый диапазон с более высокой плотностью коротких массивов. Значения будут случайными, с распределением «толстый хвост» (как в положительном, так и в отрицательном диапазонах). Дублированные элементы будут включены в некоторые тесты.
Тестовая программа доступна здесь: https://gist.github.com/anonymous/82386fa028f6534af263.
Импортирует отправку как user.c. Количество тестовых случаев ( TEST_COUNT) в фактическом тесте будет 3000. Пожалуйста, оставьте любые отзывы в комментариях к вопросу.

Срок подачи заявок: 3 недели (7 апреля 2014 года, 16:00 по Гринвичу). Я опубликую тест через 2 недели.
Может быть целесообразно размещать сообщения ближе к крайнему сроку, чтобы избежать раздачи вашего кода конкурентам.

Предварительные результаты, по состоянию на публикацию тестов:
Вот некоторые результаты. В последнем столбце отображается процентное соотношение, чем выше, тем лучше, ставя Джонни Кейджа на первое место. Алгоритмы, которые были на несколько порядков медленнее остальных, выполнялись на подмножестве тестов, и время экстраполировалось. Собственное С qsortвключено для сравнения (Джонни быстрее!). Я сделаю окончательное сравнение во время закрытия.

150 символов

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
     }
}

Сжатый.

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;}
}

150 символов (без пробелов)

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);
    }
}

67 70 69 символов

Совсем не быстро, но невероятно мало. Я полагаю, что это гибрид между сортировкой выбора и алгоритмом пузырьковой сортировки. Если вы на самом деле пытаетесь это прочитать, то вы должны знать, что ++i-v-nэто то же самое, что и ++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;
    }
}

123 символа (+3 новых строки)

Стандартная сортировка Shell, сжатая.

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: обнаружил, что это все еще в 10 раз медленнее, чем быстрая сортировка. Вы могли бы также проигнорировать эту запись.

395 символов

Сортировка слиянием.

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++;}}}

Отформатирован.

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);
     }
}

331 326 327 312 символов

Делает ли основание сортировку по 8 битам за раз. Использует причудливый битхак для правильной сортировки отрицательных чисел (украдено с http://stereopsis.com/radix.html ). Это не так компактно, но это действительно быстро (~ в 8 раз быстрее, чем самый быстрый предварительный вход). Я надеюсь на скорость, превышающую размер кода ...

#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);
}

511 424 символов

Внутренний радиксорт

Обновление: переключается на сортировку вставкой для меньших размеров массива (увеличивает производительность в 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);}

Отформатирован.

/* 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]);
}

121 114 111 символов

Просто быстрая и грязная пузырьковая сортировка с рекурсией. Вероятно, не очень эффективно.

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;}

Или длинная версия

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;
}

221 193 172 персонажа

Heapsort - не самый маленький, но на месте и гарантирует поведение O (n * log (n)).

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);
     }
}

Сжатый.

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)
}

154 166 символов

Хорошо, здесь более длинная, но более быстрая сортировка.

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;}}

Вот исправление, чтобы выжить отсортированные входы. И отформатированный, так как пробелы не учитываются.

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;
    }
}

150 символов

Шеллсорт (с Кнутом).

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;}
}

Отформатирован.

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);
}

C 270 (игра в гольф)

#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];}
}

Объяснение: Пустой массив используется для хранения каждого последующего минимального числа. Массив int - это маска с 0, указывающая, что число еще не было скопировано. После получения минимального значения маска = 1 пропускает уже использованные числа. Затем массив копируется обратно в оригинал.

Я изменил код, чтобы исключить использование библиотечных функций.

144

Я бесстыдно взял код Джонни, добавил крошечную оптимизацию и сжал код очень грязным способом. Это должно быть короче и быстрее.

Обратите внимание, что в зависимости от вашего компилятора sort (q, v + n- ++ q) должен быть заменен sort (++ q, v + nq).

#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;
    }
}

Ну, на самом деле, я начал формировать свой код и оптимизировать его, но, кажется, Джонни уже сделал правильный выбор. Так что я закончил с квази-его кодом. Я не думал о трюке с Гото, но я мог обойтись без.

228 символов

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;
    }
}