Golf + Schnelle Sortierung in C.

11

[ Letztes Update: Benchmark-Programm und vorläufige Ergebnisse verfügbar, siehe unten]

Daher möchte ich den Kompromiss zwischen Geschwindigkeit und Komplexität mit einer klassischen Anwendung testen: dem Sortieren.

Schreiben Sie eine ANSI C-Funktion, die ein Array von Gleitkommazahlen in aufsteigender Reihenfolge sortiert.

Sie können keine Bibliotheken, Systemaufrufe, Multithreading oder Inline-ASM verwenden.

Einträge werden anhand von zwei Komponenten beurteilt: Codelänge und Leistung. Bewertung wie folgt: Einträge werden nach Länge (Protokoll von #Zeichen ohne Leerzeichen, damit Sie die Formatierung beibehalten können) und nach Leistung (Protokoll von #Sekunden über einem Benchmark) sortiert und jedes Intervall [am besten, am schlechtesten] linear auf [normalisiert] 0,1]. Die Gesamtpunktzahl eines Programms ist der Durchschnitt der beiden normalisierten Punktzahlen. Die niedrigste Punktzahl gewinnt. Ein Eintrag pro Benutzer.

Die Sortierung muss (eventuell) vorhanden sein (dh das Eingabearray muss bei der Rückgabe sortierte Werte enthalten), und Sie müssen die folgende Signatur einschließlich der Namen verwenden:

void sort(float* v, int n) {

}

Zu zählende Zeichen: diejenigen in der sortFunktion, einschließlich Signatur, plus zusätzliche Funktionen, die von ihr aufgerufen werden (jedoch ohne Testcode).

Das Programm muss alle numerischen Werte floatund Arrays mit einer Länge von> = 0 bis zu 2 ^ 20 verarbeiten.

Ich werde sortund seine Abhängigkeiten in ein Testprogramm einbinden und auf GCC kompilieren (keine ausgefallenen Optionen). Ich werde eine Reihe von Arrays einspeisen, die Richtigkeit der Ergebnisse und die Gesamtlaufzeit überprüfen. Die Tests werden auf einem Intel Core i7 740QM (Clarksfield) unter Ubuntu 13 ausgeführt. Die
Array-Längen erstrecken sich über den gesamten zulässigen Bereich mit einer höheren Dichte an kurzen Arrays. Die Werte sind zufällig mit einer Fettschwanzverteilung (sowohl im positiven als auch im negativen Bereich). Doppelte Elemente werden in einigen Tests enthalten sein.
Das Testprogramm ist hier verfügbar: https://gist.github.com/anonymous/82386fa028f6534af263
Es importiert die Einreichung als user.c. Die Anzahl der Testfälle ( TEST_COUNT) im aktuellen Benchmark beträgt 3000. Bitte geben Sie in den Fragenkommentaren Feedback.

Frist: 3 Wochen (7. April 2014, 16:00 GMT). Ich werde den Benchmark in 2 Wochen veröffentlichen.
Es kann ratsam sein, kurz vor Ablauf der Frist zu posten, um zu vermeiden, dass Ihr Code an Mitbewerber weitergegeben wird.

Vorläufige Ergebnisse zum Zeitpunkt der Veröffentlichung der Benchmark:
Hier einige Ergebnisse. In der letzten Spalte wird die Punktzahl als Prozentsatz angezeigt. Je höher desto besser, wobei Johnny Cage an erster Stelle steht. Algorithmen, die um Größenordnungen langsamer waren als die anderen, wurden in einer Teilmenge von Tests ausgeführt und die Zeit extrapoliert. Cs eigene qsortist zum Vergleich enthalten (Johnny's ist schneller!). Ich werde zum Abschluss einen abschließenden Vergleich durchführen.

Geben Sie hier die Bildbeschreibung ein

Mau
quelle
3
Können Sie den Benchmark angeben? Verschiedene Sortierfunktionen arbeiten je nach Art der Daten unterschiedlich. ZB ist die Blasensortierung für winzige Arrays schneller als die stdlib-Quicksortierung. Wir möchten möglicherweise für Ihren Benchmark optimieren.
Claudiu
@Claudiu Ich habe einmal eine schöne Kurzversion von Quicksort gesehen, die genauso gut lief wie jede andere auf Daten, bei denen jedes Element anders war. Aber wenn einige Elemente gleich waren, lief es im absoluten Schneckentempo. Ich spreche nicht über das bekannte Problem der schlechten Wahl des Pivots in sortierten / teilweise sortierten Arrays. Meine Testdaten wurden völlig zufällig gemischt. Diese spezielle Version mochte keine Duplikate. Seltsam, aber wahr.
Level River St
3
Willkommen bei PPCG! Wir verbieten zwar keine sprachspezifischen Herausforderungen, empfehlen jedoch nachdrücklich, Fragen möglichst sprachunabhängig zu formulieren. Betrachten Sie es für Ihre nächste Frage und haben Sie Spaß mit dieser!
Jonathan Van Matre
1
@steveverrill: Ich folge nicht. Es spielt keine Rolle, was Ihre Einheit ist, da Sie sie sowieso von 0 auf 1 skalieren. Wenn min 1 Stunde und max 3 Stunden beträgt, beträgt etwas, das 1,5 Stunden dauert, 0,25, unabhängig davon, ob min 60 Minuten, max 180 Minuten und 90 Minuten beträgt
Claudiu
1
OP sagte nur keine Inline-Montage - er sagte nichts über Intrinsics.
Paul R

Antworten:

6

150 Zeichen

Schnelle Sorte.

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

Komprimiert.

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;}
}
Johnny Cage
quelle
Das Rennen führen!
Mau
3

150 Zeichen (ohne Leerzeichen)

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);
    }
}
Michael M.
quelle
Super, erster Eintrag!
Mau
Fühlen Sie sich frei, eine Antwort mit SSE zu posten, und ich werde sie in der Anzeigetafel auflisten, obwohl ich an "tragbaren" Lösungen für die Herausforderung interessiert bin.
Mau
if(*w<*v) { t=v[++l]; v[l]=*w; *w=t; }kann seinif(*w<*v) t=v[++l], v[l]=*w, *w=t;
ASKASK
3

67 70 69 Zeichen

Überhaupt nicht schnell, aber unglaublich klein. Es ist eine Mischung aus einer Auswahlsortierung und einem Blasensortierungsalgorithmus, denke ich. Wenn Sie tatsächlich versuchen, dies zu lesen, sollten Sie wissen, dass dies ++i-v-ndasselbe ist wie ++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;
    }
}
BITTE
quelle
if(a)b-> a?b:0speichert ein Zeichen.
Ugoren
Nun, das ++i-v-nist ++i != v+nnatürlich das Gleiche wie nur in einer Bedingung.
Wchargin
@ugoren Ich denke, Sie haben diesen Kommentar zu der falschen Antwort gepostet
ASKASK
@ ASKASK, if(*i>v[n])...->*i>v[n]?...:0
ugoren
Sind Sie sicher, dass die Präsenz so funktioniert?
Fragen Sie
2

123 Zeichen (+3 Zeilenumbrüche)

Eine Standard-Shell-Sortierung, komprimiert.

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: entdeckt, dass es immer noch 10x langsamer als Quicksort ist. Sie können diesen Eintrag auch ignorieren.

Florian F.
quelle
Ihre Wahl der Lücken könnte besser sein. Das ist wahrscheinlich der Grund, warum dies viel langsamer ist als Quicksort. en.wikipedia.org/wiki/Shellsort#Gap_sequences
FDinoff
Ich war erstaunt zu entdecken, wie sehr die Lückenfolge die Geschwindigkeit beeinflusst. Mit einer guten Sequenz kommt es dem Quicksort nahe, bleibt aber meiner Erfahrung nach langsamer.
Florian F
Sei nicht zu hart mit dir. Du bist auf dem dritten Platz.
Kevin
2

395 Zeichen

Zusammenführen, sortieren.

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

Formatiert.

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);
     }
}
Knöchel Sandwich
quelle
2

331 326 327 312 Zeichen

Sortiert Radix 8 Bits gleichzeitig. Verwendet einen ausgefallenen Bithack, um negative Floats korrekt zu sortieren (gestohlen von http://stereopsis.com/radix.html ). Es ist nicht so kompakt, aber es ist sehr schnell (~ 8x schneller als der schnellste vorläufige Eintrag). Ich hoffe auf eine Geschwindigkeit, die den Code übertrifft ...

#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);
}
Keith Randall
quelle
2

511 424 Zeichen

Radixsort einbauen

Update: Wechselt bei kleineren Array-Größen zur Einfügesortierung (erhöht die Benchmark-Leistung um den Faktor 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);}

Formatiert.

/* 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]);
}
MojoJojoBojoHojo
quelle
Nett! Versuchen Sie, die ursprüngliche Antwort zu markieren.
Mau
@ Mau: Danke und werde es tun. Wollte einen Fehler im Benchmarking-Code erwähnen. Die Umwandlung void*in qsort(Zeile 88) wirft die Zeigerarithmetik ab.
MojoJojoBojoHojo
1

121 114 111 Zeichen

Nur eine schnelle und schmutzige Blasensortierung mit Rekursion. Wahrscheinlich nicht sehr effizient.

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

Oder die lange 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;
}
CompuChip
quelle
Nebenbei habe ich hier einen wirklich interessanten Algorithmus gefunden: rosettacode.org/wiki/Sorting_algorithms/Pancake_sort#C Aber ich kann ihn nicht genug komprimieren, um 114 zu schlagen :)
CompuChip
Ihr Programm scheint in einigen Fällen nicht vollständig zu sein und in anderen Fällen außerhalb der Grenzen zu schreiben.
Mau
@Mau Ich habe es an einigen Eingaben manuell getestet und schien in Ordnung zu funktionieren, aber aus Zeitgründen habe ich es nicht sehr gründlich getestet, sodass ich sicher bin, dass es irgendwo ein schlechtes Verhalten gibt. Könnten Sie bitte einen Testfall posten, bei dem Sie auf Probleme gestoßen sind?
CompuChip
Testprogramm oben verfügbar :)
Mau
Hmm, ich habe versucht, es auszuführen. Ich erhalte einige "munmap_chunk (): ungültige Zeiger" -Fehler im Bereinigungsteil, aber nichts über den fehlgeschlagenen Test. Sie haben jedoch Recht, dass ein Fehler nach dem anderen vorliegt, und ich habe anscheinend einige Sequenzierungsprobleme (die durch Kommas getrennte Liste von Anweisungen entspricht nicht meinen Erwartungen). Ich werde versuchen, es zu beheben.
CompuChip
1

221 193 172 Zeichen

Heapsort - Nicht das kleinste, aber vorhanden und garantiert O (n * log (n)) Verhalten.

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

Komprimiert.

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)
}
user19425
quelle
Sie können einige Zeichen speichern, indem Sie das Leerzeichen abziehen. Und möglicherweise auch die obligatorische Funktionssignatur, aber da einige Einträge gezählt haben, habe ich den Fragesteller gebeten, zu klären, ob sie gezählt werden sollen.
Jonathan Van Matre
@ user19425: Wenn Sie das Testprogramm mit TEST_COUNT= 3000 ausführen , scheint mindestens ein Test fehlgeschlagen zu sein.
Mau
1

154 166 Zeichen

OK, hier ist eine längere, aber schnellere Quicksortierung.

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

Hier ist eine Korrektur, um sortierte Eingaben zu überleben. Und formatiert, da Leerzeichen nicht zählen.

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;
    }
}
Florian F.
quelle
Diese Version scheint in einigen Fällen außerhalb der Grenzen zu schreiben und in anderen nicht zu enden.
Mau
PS: OK, bei einem sortierten Satz ist es sehr langsam. Die Problemstellung besagt jedoch, dass die Eingabe zufällig ist.
Florian F
Die Werte sind zufällig. Ich habe nie etwas darüber gesagt, in welcher Reihenfolge sie sein würden :-) Aber ja, es gibt Blöcke, die ungefähr 10% aller Werte in aufsteigender Reihenfolge und weitere 10% in absteigender Reihenfolge abdecken.
Mau
1
Meinetwegen. Und eine sort () sollte für sortierte Eingaben funktionieren. Ich werde meine Einreichung aktualisieren, dann ...
Florian F
1

150 Zeichen

Shellsort (mit Knuth-Lücke).

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

Formatiert.

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);
}
SineDog
quelle
1

C 270 (Golf)

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

Erläuterung: In einem leeren Array wird jede aufeinanderfolgende Mindestanzahl gespeichert. Ein int-Array ist eine Maske mit 0, die angibt, dass die Nummer noch nicht kopiert wurde. Nach Erhalt des Mindestwerts überspringt eine Maske = 1 bereits verwendete Zahlen. Anschließend wird das Array wieder in das Original kopiert.

Ich habe den Code geändert, um die Verwendung von Bibliotheksfunktionen zu vermeiden.

Bacchusbeale
quelle
0

144

Ich nahm schamlos Johnnys Code, fügte eine winzige Optimierung hinzu und komprimierte den Code auf sehr schmutzige Weise. Es sollte kürzer und schneller sein.

Beachten Sie, dass je nach Compiler die Sortierung (q, v + n- ++ q) durch die Sortierung (++ q, v + nq) ersetzt werden muss.

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

Eigentlich habe ich angefangen, meinen Code zu formen und ihn zu optimieren, aber anscheinend hat Johnny bereits die richtigen Entscheidungen getroffen. Also habe ich quasi seinen Code erhalten. Ich habe nicht an den Goto-Trick gedacht, aber ich konnte darauf verzichten.

Florian F.
quelle
0

228 Zeichen

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