Domanda

Se possibile, come posso migliorare il seguente quick sort (prestazioni saggio). Eventuali suggerimenti? 

void main()
    {
      quick(a,0,n-1);
    }

    void quick(int a[],int lower,int upper)
    {
       int loc;
       if(lower<upper)
       {
        loc=partition(a,lower,upper);
        quick(a,lower,loc-1);
        quick(a,loc+1,upper);

       }
    }

    /* Return type: int
      Parameters passed: Unsorted array and its lower and upper bounds */

    int partition(int a[],int lower,int upper)
    {
      int pivot,i,j,temp;
      pivot=a[lower];
      i=lower+1;
      j=upper;
      while(i<j)
        {
            while((i<upper)&&(a[i]<=pivot))
            i++;
            while((a[j]>pivot))
            j--;
            if(i<j)
                {
                    temp=a[i];
                    a[i]=a[j];
                    a[j]=temp;
                }

        }//end while

        if(pivot>a[j])
        {
             temp=a[j];
             a[j]=a[lower];
             a[lower]=temp;
        }

         return(j);

}//end partition
È stato utile?

Soluzione

L'algoritmo quicksort è facilmente parallelizzata. Se si dispone di più core con cui lavorare, si poteva vedere un po 'di velocità in su. A seconda di quanto è grande il set di dati è, si potrebbe facilmente fornire con più velocità fino di ogni altra ottimizzazione. Tuttavia, se si dispone di un solo processore o un relativamente piccolo insieme di dati, non ci sarà più di una velocità fino.

ho potuto elaborare più se questa è una possibilità.

Altri suggerimenti

  1. Scegli un perno meglio: ad es. in mediana-di-tre si sceglie 3 elementi (casuali) e scegliere il pivot come l'elemento mediano
  2. Quando la lunghezza (a [])

Il primo suggerimento sarebbe: sostituire una delle chiamate ricorsive con iterazione. E voglio dire vero iterazione, non uno stack implementato manualmente per ricorsione. Cioè invece di fare due "nuovi" chiamate a quick da quick, "riciclare" il tuo corrente chiamata a quick per elaborare un ramo della ricorsione, e chiamare quick ricorsivamente per elaborare un altro ramo.

Ora, se fate in modo che si fanno sempre vera chiamata ricorsiva per il più breve partizione (e utilizzare l'iterazione per quello più lungo), si garantirà che la profondità della ricorsione non supererà mai log N nemmeno nel caso peggiore, cioè indipendentemente da quanto bene di scegliere il vostro mediana.

Il tutto è implementato in algoritmo qsort che viene fornito con libreria standard GCC. Date un'occhiata alla fonte, dovrebbe essere utile.

Approssimativamente, un'implementazione più pratica che segue il suggerimento sopra potrebbe apparire come segue 

void quick(int a[], int lower, int upper)
{
  while (lower < upper)
  {
    int loc = partition(a, lower, upper);
    if (loc - lower < upper - loc)
    { /* Lower part is shorter... */
      quick(a, lower, loc - 1); /* ...process it recursively... */
      lower = loc + 1; /* ...and process the upper part on the next iteration */
    }
    else
    { /* Upper part is shorter... */
      quick(a, loc + 1, upper); /* ...process it recursively... */
      upper = loc - 1; /* ...and process the lower part on the next iteration */
    }
  }
}

Questa è solo un abbozzo dell'idea, naturalmente. Non testato. Anche in questo caso, dare un'occhiata a implementazione GCC per la stessa idea. Essi hanno inoltre sostituire la chiamata ricorsiva restante con ricorsione "manuale", ma non è davvero necessario.

Ordinamento piccoli blocchi (<5 elementi) con un algoritmo loopless può migliorare le prestazioni. Ho trovato solo un esempio di come scrivere un algoritmo di ordinamento loopless per 5 elementi: http://wiki.tcl.tk/ 4118

L'idea può essere utilizzato per generare algoritmi loopless smistamento per 2,3,4,5 elementi C.

EDIT: ho provato su un insieme di dati, e ho misurato 87% tempo di esecuzione rispetto al codice in questione. Utilizzare l'inserimento ordinamento <20 blocchi portato 92% sullo stesso insieme di dati. Questa misura non è rappresentativo, ma può dimostrare che questo è un modo come è possibile migliorare il tuo codice di quicksort.

EDIT: questo codice di esempio scrivere funzioni loopless di smistamento per 2-6 elementi: 

#include <stdio.h>

#define OUT(i,fmt,...)  printf("%*.s"fmt"\n",i,"",##__VA_ARGS__);

#define IF( a,b, i, block1, block2 ) \
  OUT(i,"if(t[%i]>t[%i]){",a,b) block1 OUT(i,"}else{") block2 OUT(i,"}")

#define AB2(i,a,b)         IF(a,b,i,P2(i+2,b,a),P2(i+2,a,b))
#define  P2(i,a,b)         print_perm(i,2,(int[2]){a,b});

#define AB3(i,a,b,c)       IF(a,b,i,BC3(i+2,b,a,c),BC3(i+2,a,b,c))
#define AC3(i,a,b,c)       IF(a,c,i, P3(i+2,c,a,b), P3(i+2,a,c,b))
#define BC3(i,a,b,c)       IF(b,c,i,AC3(i+2,a,b,c), P3(i+2,a,b,c))
#define  P3(i,a,b,c)       print_perm(i,3,(int[3]){a,b,c});

#define AB4(i,a,b,c,d)     IF(a,b,i,CD4(i+2,b,a,c,d),CD4(i+2,a,b,c,d))
#define AC4(i,a,b,c,d)     IF(a,c,i, P4(i+2,c,a,b,d), P4(i+2,a,c,b,d))
#define BC4(i,a,b,c,d)     IF(b,c,i,AC4(i+2,a,b,c,d), P4(i+2,a,b,c,d))
#define BD4(i,a,b,c,d)     IF(b,d,i,BC4(i+2,c,d,a,b),BC4(i+2,a,b,c,d))
#define CD4(i,a,b,c,d)     IF(c,d,i,BD4(i+2,a,b,d,c),BD4(i+2,a,b,c,d))
#define  P4(i,a,b,c,d)     print_perm(i,4,(int[4]){a,b,c,d});

#define AB5(i,a,b,c,d,e)   IF(a,b,i,CD5(i+2,b,a,c,d,e),CD5(i+2,a,b,c,d,e))
#define AC5(i,a,b,c,d,e)   IF(a,c,i, P5(i+2,c,a,b,d,e), P5(i+2,a,c,b,d,e))
#define AE5(i,a,b,c,d,e)   IF(a,e,i,CB5(i+2,e,a,c,b,d),CB5(i+2,a,e,c,b,d))
#define BE5(i,a,b,c,d,e)   IF(b,e,i,AE5(i+2,a,b,c,d,e),DE5(i+2,a,b,c,d,e))
#define BD5(i,a,b,c,d,e)   IF(b,d,i,BE5(i+2,c,d,a,b,e),BE5(i+2,a,b,c,d,e))
#define CB5(i,a,b,c,d,e)   IF(c,b,i,DC5(i+2,a,b,c,d,e),AC5(i+2,a,b,c,d,e))
#define CD5(i,a,b,c,d,e)   IF(c,d,i,BD5(i+2,a,b,d,c,e),BD5(i+2,a,b,c,d,e))
#define DC5(i,a,b,c,d,e)   IF(d,c,i, P5(i+2,a,b,c,d,e), P5(i+2,a,b,d,c,e))
#define DE5(i,a,b,c,d,e)   IF(d,e,i,CB5(i+2,a,b,c,e,d),CB5(i+2,a,b,c,d,e))
#define  P5(i,a,b,c,d,e)   print_perm(i,5,(int[5]){a,b,c,d,e});

#define AB6(i,a,b,c,d,e,f) IF(a,b,i,CD6(i+2,b,a,c,d,e,f),CD6(i+2,a,b,c,d,e,f))
#define AC6(i,a,b,c,d,e,f) IF(a,c,i, P6(i+2,c,a,b,d,e,f), P6(i+2,a,c,b,d,e,f))
#define AE6(i,a,b,c,d,e,f) IF(a,e,i,CB6(i+2,e,a,c,b,d,f),CB6(i+2,a,e,c,b,d,f))
#define BD6(i,a,b,c,d,e,f) IF(b,d,i,DF6(i+2,c,d,a,b,e,f),DF6(i+2,a,b,c,d,e,f))
#define BE6(i,a,b,c,d,e,f) IF(b,e,i,AE6(i+2,a,b,c,d,e,f),DE6(i+2,a,b,c,d,e,f))
#define CB6(i,a,b,c,d,e,f) IF(c,b,i,DC6(i+2,a,b,c,d,e,f),AC6(i+2,a,b,c,d,e,f))
#define CD6(i,a,b,c,d,e,f) IF(c,d,i,EF6(i+2,a,b,d,c,e,f),EF6(i+2,a,b,c,d,e,f))
#define DB6(i,a,b,c,d,e,f) IF(d,b,i,BE6(i+2,a,b,c,d,e,f),BE6(i+2,c,d,a,b,e,f))
#define DC6(i,a,b,c,d,e,f) IF(d,c,i, P6(i+2,a,b,c,d,e,f), P6(i+2,a,b,d,c,e,f))
#define DE6(i,a,b,c,d,e,f) IF(d,e,i,CB6(i+2,a,b,c,e,d,f),CB6(i+2,a,b,c,d,e,f))
#define DF6(i,a,b,c,d,e,f) IF(d,f,i,DB6(i+2,a,b,e,f,c,d),BE6(i+2,a,b,c,d,e,f))
#define EF6(i,a,b,c,d,e,f) IF(e,f,i,BD6(i+2,a,b,c,d,f,e),BD6(i+2,a,b,c,d,e,f))
#define  P6(i,a,b,c,d,e,f) print_perm(i,6,(int[6]){a,b,c,d,e,f});

#define SORT(ABn,n,...) \
  OUT( 0, ""); \
  OUT( 0, "inline void sort" #n "( int t[" #n "] ){" ) \
  OUT( 2, "int tmp;" ) \
  ABn( 2, __VA_ARGS__ ) \
  OUT( 0, "}" )

void print_perm( int ind, int n, int t[n] ){
  printf("%*.s", ind-1, "");
  for( int i=0; i<n; i++ )
    if( i != t[i] ){
      printf(" tmp=t[%i]; t[%i]=",i,i);
      for( int j=t[i],k; j!=i; k=j,j=t[j],t[k]=k)
        printf("t[%i]; t[%i]=",j,j);
      printf("tmp;");
    }
  printf("\n");
}

int main( void ){
  SORT( AB2, 2, 0,1 )
  SORT( AB3, 3, 0,1,2 )
  SORT( AB4, 4, 0,1,2,3 )
  SORT( AB5, 5, 0,1,2,3,4 )
  SORT( AB6, 6, 0,1,2,3,4,5 )
}

Il codice generato 3718 linee lungo: 

sort2():    8
sort3():   24
sort4():   96
sort5():  512
sort6(): 3072

Provare con un altro algoritmo di ordinamento.

A seconda dei dati, si può essere in grado di scambiare la memoria per la velocità.

Secondo Wikipedia

  • quick sort ha un migliore dei casi O (n log n) prestazioni e O (1) spazio
  • merge sort ha una O fisso (n log n) le prestazioni e la O (n) spazio
  • Radix ha sorta un O fisso (n. ) perfomance e O (n. ) spazio

Modifica

A quanto pare i vostri dati sono numeri interi. Con 2.5M interi nel range [0, 0x0fffffff], la mia implementazione di Radix-tipo è circa 4 volte più veloce l'implementazione di quick-sort. 

$ ./a.out
qsort time: 0.39 secs
radix time: 0.09 secs
good: 2000; evil: 0

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define ARRAY_SIZE 2560000
#define RANDOM_NUMBER (((rand() << 16) + rand()) & 0x0fffffff)

int partition(int a[], int lower, int upper) {
  int pivot, i, j, temp;
  pivot = a[lower];
  i = lower + 1;
  j = upper;
  while (i < j) {
    while((i < upper) && (a[i] <= pivot)) i++;
    while (a[j] > pivot) j--;
    if (i < j) {
      temp = a[i];
      a[i] = a[j];
      a[j] = temp;
    }
  }
  if (pivot > a[j]) {
    temp = a[j];
    a[j] = a[lower];
    a[lower] = temp;
  }
  return j;
}

void quick(int a[], int lower, int upper) {
  int loc;
  if (lower < upper) {
    loc = partition(a, lower, upper);
    quick(a, lower, loc-1);
    quick(a, loc+1, upper);
  }
}

#define NBUCKETS 256
#define BUCKET_SIZE (48 * (1 + ARRAY_SIZE / NBUCKETS))

/* "waste" memory */
int bucket[NBUCKETS][BUCKET_SIZE];

void radix(int *a, size_t siz) {
  unsigned shift = 0;
  for (int dummy=0; dummy<4; dummy++) {
    int bcount[NBUCKETS] = {0};
    int *aa = a;
    size_t s = siz;
    while (s--) {
      unsigned v = ((unsigned)*aa >> shift) & 0xff;
      if (bcount[v] == BUCKET_SIZE) {
        fprintf(stderr, "not enough memory.\n");
        fprintf(stderr, "v == %u; bcount[v] = %d.\n", v, bcount[v]);
        exit(EXIT_FAILURE);
      }
      bucket[v][bcount[v]++] = *aa++;
    }
    aa = a;
    for (int k=0; k<NBUCKETS; k++) {
      for (int j=0; j<bcount[k]; j++) *aa++ = bucket[k][j];
    }
    shift += 8;
  }
}

int ar1[ARRAY_SIZE];
int ar2[ARRAY_SIZE];

int main(void) {
  clock_t t0;

  srand(time(0));
  for (int k=0; k<ARRAY_SIZE; k++) ar1[k] = ar2[k] = RANDOM_NUMBER;

  t0 = clock(); while (clock() == t0) /* void */; t0 = clock();
  do {
    quick(ar1, 0, ARRAY_SIZE - 1);
  } while (0);
  double qsort_time = (double)(clock() - t0) / CLOCKS_PER_SEC;

  t0 = clock(); while (clock() == t0) /* void */; t0 = clock();
  do {
    radix(ar2, ARRAY_SIZE);
  } while (0);
  double radix_time = (double)(clock() - t0) / CLOCKS_PER_SEC;

  printf("qsort time: %.2f secs\n", qsort_time);
  printf("radix time: %.2f secs\n", radix_time);

  /* compare sorted arrays by sampling */
  int evil = 0;
  int good = 0;
  for (int chk=0; chk<2000; chk++) {
    size_t index = RANDOM_NUMBER % ARRAY_SIZE;
    if (ar1[index] == ar2[index]) good++;
    else evil++;
  }
  printf("good: %d; evil: %d\n", good, evil);

  return 0;
}

Il Wikipedia articolo su quicksort ha un sacco di idee.

  1. È possibile eliminare un recuriosn testa utilizzando QuickSort con esplicita Stack 

    void quickSort(int a[], int lower, int upper)
{
    createStack(); 
    push(lower); 
    push(upper);

    while (!isEmptyStack()) {
    upper=poptop();
    lower=poptop();
       while (lower<upper) {
                 pivPos=partition(selectPivot(a, size), a, lower, upper);
                 push(lower);
                 push(pivPos-1);
                 lower = pivPos+1; // end = end;
       }
   }
}

  2. È possibile utilizzare una migliore tecnica di selezione perno come ad esempio:

    1. mediano di 3
    2. bfprt
    3. perno casuale

Attualmente il Quicksort più avanzato ampiamente utilizzato è implementato in Java DualPivotQuicksort.java Così si può semplicemente seguire tale approccio e si vedrà un bel miglioramento delle prestazioni:

  • Utilizza l'inserimento di ordinamento per piccoli array (47 è il numero utilizzato in Java)
  • Usa che Quicksort dual-perno scegliendo il 2 ° e 4 ° elementi su 5, come i due perni
  • Considerare l'utilizzo mergesort per array con corse di numeri ordinati

In alternativa, se si desidera aggiungere un po 'di più la complessità quindi codificare un 3-perno Quicksort .

Se questo non è solo per imparare l'uso qsort da stdlib.h

Per il codice, quando lunghezza ordinato è 10, lo stack più profondo appare come 

#0  partition (a=0x7fff5ac42180, lower=3, upper=5) 
#1  0x000000000040062f in quick (a=0x7fff5ac42180, lower=3, upper=5) 
#2  0x0000000000400656 in quick (a=0x7fff5ac42180, lower=0, upper=5) 
#3  0x0000000000400644 in quick (a=0x7fff5ac42180, lower=0, upper=8) 
#4  0x0000000000400644 in quick (a=0x7fff5ac42180, lower=0, upper=9) 
#5  0x00000000004005c3 in main

Oltre al algo stesso, se si considera il comportamento del sistema come ad esempio le attività di stack così, qualcos'altro tranne i normali costi di stack di chiamate (push / pop) potrebbe declassare le prestazioni un sacco, per esempio cambio di contesto se il sistema multi-task, si sa la maggior parte OS sono multi-task, e più profondo lo stack più alto costa alla commutazione, oltre a perdere la cache o cachline confine attraverso.

Io credo in questo caso se la lunghezza diventare più grande, si perde quando si confrontano ad alcuni altri algos ordinamento.

per esempio, quando la lunghezza è fino a 40, la pila potrebbe sembrare (può più voci rispetto a quanto mostrato come sotto): 

#0  partition (a=0x7fff24810cd0, lower=8, upper=9) 
#1  0x000000000040065d in quick (a=0x7fff24810cd0, lower=8, upper=9)  
#2  0x0000000000400672 in quick (a=0x7fff24810cd0, lower=8, upper=10) 
#3  0x0000000000400672 in quick (a=0x7fff24810cd0, lower=8, upper=14) 
#4  0x0000000000400684 in quick (a=0x7fff24810cd0, lower=4, upper=14) 
#5  0x0000000000400672 in quick (a=0x7fff24810cd0, lower=4, upper=18) 
#6  0x0000000000400684 in quick (a=0x7fff24810cd0, lower=0, upper=18) 
#7  0x0000000000400672 in quick (a=0x7fff24810cd0, lower=0, upper=26) 
#8  0x0000000000400672 in quick (a=0x7fff24810cd0, lower=0, upper=38) 
#9  0x0000000000400672 in quick (a=0x7fff24810cd0, lower=0, upper=39) 
#10 0x00000000004005ee in main

troppo profondo dello stack.

inlining La funzione è utile anche, ma aumenta il codice impronta del file eseguibile finale. Sono d'accordo con @Swiss, la programmazione parallela potrebbe aiutare a tanto.

risposta completamente muto, ma ... compilare il codice in modalità di rilascio e accendere ottimizzazioni!

La prima cosa da fare è punto di riferimento di esso. E punto di riferimento contro il qsort standard e contro il C ++ std :: sort e std :: stable_sort.

I risultati, se il vostro data-set di essere abbastanza grande, mostrerà che lo std :: sort è superiore a qsort in tutti i casi ad eccezione di quelli , dove lo std :: stable_sort è superiore. Questo perché lo std :: ordinamento è basato su modelli, e quindi il confronto può essere inline.

Il codice inline il confronto perché la sua non generico. Se il codice è più lento di qsort, hai un problema proprio lì.

L'ordinamento veloce sarebbe ordinare parti in parallelo, ad esempio OpenMP, e poi unirle di nuovo insieme.

Copiato da mia risposta per rispondere alla domanda.

Modifica:. Questo post presuppone che già fare le cose ovvie come approfittare della ricorsione in coda per sbarazzarsi della chiamata inutile sovraccarico

Persone come critica la Quicksort per scarso rendimento con determinati input, specialmente quando l'utente ha il controllo dell'ingresso. Il seguente approccio produce prestazioni corrispondenti selezione punto medio, ma prevede la complessità in modo esponenziale si avvicina O ( n Registro n ) come la lista cresce in dimensioni. Nella mia esperienza supera in modo significativo best-of-3 selezione a causa di molto meno overhead nel caso di maggioranza. Dovrebbe eseguire uniformemente con selezione punto medio per gli ingressi "attesa", ma non è vulnerabile agli ingressi poveri.

  • Inizializzare il Quicksort con un I intero positivo casuale. Tale valore verrà utilizzato durante tutto il processo di smistamento (non hanno di generare più numeri).
  • Pivot è selezionato come I mod SectionSize.

Per prestazioni aggiuntive, si dovrebbe sempre passare il quicksort a sborsare di ordinamento per i segmenti della lista "piccoli" -. Ho visto lunghezze da 15-100 scelto come cutoff

multithreading? 

/*
 * multiple-thread quick-sort.
 * Works fine on uniprocessor machines as well.
 */

#include <unistd.h>
#include <stdlib.h>
#include <thread.h>

/* don't create more threads for less than this */
#define SLICE_THRESH   4096

/* how many threads per lwp */
#define THR_PER_LWP       4

/* cast the void to a one byte quanitity and compute the offset */
#define SUB(a, n)      ((void *) (((unsigned char *) (a)) + ((n) * width)))

typedef struct {
  void    *sa_base;
  int      sa_nel;
  size_t   sa_width;
  int    (*sa_compar)(const void *, const void *);
} sort_args_t;

/* for all instances of quicksort */
static int threads_avail;

#define SWAP(a, i, j, width)
{ 
  int n; 
  unsigned char uc; 
  unsigned short us; 
  unsigned long ul; 
  unsigned long long ull; 

  if (SUB(a, i) == pivot) 
    pivot = SUB(a, j); 
  else if (SUB(a, j) == pivot) 
    pivot = SUB(a, i); 

  /* one of the more convoluted swaps I've done */ 
  switch(width) { 
  case 1: 
    uc = *((unsigned char *) SUB(a, i)); 
    *((unsigned char *) SUB(a, i)) = *((unsigned char *) SUB(a, j)); 
    *((unsigned char *) SUB(a, j)) = uc; 
    break; 
  case 2: 
    us = *((unsigned short *) SUB(a, i)); 
    *((unsigned short *) SUB(a, i)) = *((unsigned short *) SUB(a, j)); 
    *((unsigned short *) SUB(a, j)) = us; 
    break; 
  case 4: 
    ul = *((unsigned long *) SUB(a, i)); 
    *((unsigned long *) SUB(a, i)) = *((unsigned long *) SUB(a, j)); 
    *((unsigned long *) SUB(a, j)) = ul; 
    break; 
  case 8: 
    ull = *((unsigned long long *) SUB(a, i)); 
    *((unsigned long long *) SUB(a,i)) = *((unsigned long long *) SUB(a,j)); 
    *((unsigned long long *) SUB(a, j)) = ull; 
    break; 
  default: 
    for(n=0; n<width; n++) { 
      uc = ((unsigned char *) SUB(a, i))[n]; 
      ((unsigned char *) SUB(a, i))[n] = ((unsigned char *) SUB(a, j))[n]; 
      ((unsigned char *) SUB(a, j))[n] = uc; 
    } 
    break; 
  } 
}

static void *
_quicksort(void *arg)
{
  sort_args_t *sargs = (sort_args_t *) arg;
  register void *a = sargs->sa_base;
  int n = sargs->sa_nel;
  int width = sargs->sa_width;
  int (*compar)(const void *, const void *) = sargs->sa_compar;
  register int i;
  register int j;
  int z;
  int thread_count = 0;
  void *t;
  void *b[3];
  void *pivot = 0;
  sort_args_t sort_args[2];
  thread_t tid;

  /* find the pivot point */
  switch(n) {
  case 0:
  case 1:
    return 0;
  case 2:
    if ((*compar)(SUB(a, 0), SUB(a, 1)) > 0) {
      SWAP(a, 0, 1, width);
    }
    return 0;
  case 3:
    /* three sort */
    if ((*compar)(SUB(a, 0), SUB(a, 1)) > 0) {
      SWAP(a, 0, 1, width);
    }
    /* the first two are now ordered, now order the second two */
    if ((*compar)(SUB(a, 2), SUB(a, 1)) < 0) {
      SWAP(a, 2, 1, width);
    }
    /* should the second be moved to the first? */
    if ((*compar)(SUB(a, 1), SUB(a, 0)) < 0) {
      SWAP(a, 1, 0, width);
    }
    return 0;
  default:
    if (n > 3) {
      b[0] = SUB(a, 0);
      b[1] = SUB(a, n / 2);
      b[2] = SUB(a, n - 1);
      /* three sort */
      if ((*compar)(b[0], b[1]) > 0) {
        t = b[0];
        b[0] = b[1];
        b[1] = t;
      }
      /* the first two are now ordered, now order the second two */
      if ((*compar)(b[2], b[1]) < 0) {
        t = b[1];
        b[1] = b[2];
        b[2] = t;
      }
      /* should the second be moved to the first? */
      if ((*compar)(b[1], b[0]) < 0) {
        t = b[0];
        b[0] = b[1];
        b[1] = t;
      }
      if ((*compar)(b[0], b[2]) != 0)
        if ((*compar)(b[0], b[1]) < 0)
          pivot = b[1];
        else
          pivot = b[2];
    }
    break;
  }
  if (pivot == 0)
    for(i=1; i<n; i++) {
      if (z = (*compar)(SUB(a, 0), SUB(a, i))) {
        pivot = (z > 0) ? SUB(a, 0) : SUB(a, i);
        break;
      }
    }
  if (pivot == 0)
    return;

  /* sort */
  i = 0;
  j = n - 1;
  while(i <= j) {
    while((*compar)(SUB(a, i), pivot) < 0)
      ++i;
    while((*compar)(SUB(a, j), pivot) >= 0)
      --j;
    if (i < j) {
      SWAP(a, i, j, width);
      ++i;
      --j;
    }
  }

  /* sort the sides judiciously */
  switch(i) {
  case 0:
  case 1:
    break;
  case 2:
    if ((*compar)(SUB(a, 0), SUB(a, 1)) > 0) {
      SWAP(a, 0, 1, width);
    }
    break;
  case 3:
    /* three sort */
    if ((*compar)(SUB(a, 0), SUB(a, 1)) > 0) {
      SWAP(a, 0, 1, width);
    }
    /* the first two are now ordered, now order the second two */
    if ((*compar)(SUB(a, 2), SUB(a, 1)) < 0) {
      SWAP(a, 2, 1, width);
    }
    /* should the second be moved to the first? */
    if ((*compar)(SUB(a, 1), SUB(a, 0)) < 0) {
      SWAP(a, 1, 0, width);
    }
    break;
  default:
    sort_args[0].sa_base          = a;
    sort_args[0].sa_nel           = i;
    sort_args[0].sa_width         = width;
    sort_args[0].sa_compar        = compar;
    if ((threads_avail > 0) && (i > SLICE_THRESH)) {
      threads_avail--;
      thr_create(0, 0, _quicksort, &sort_args[0], 0, &tid);
      thread_count = 1;
    } else
      _quicksort(&sort_args[0]);
    break;
  }
  j = n - i;
  switch(j) {
  case 1:
    break;
  case 2:
    if ((*compar)(SUB(a, i), SUB(a, i + 1)) > 0) {
      SWAP(a, i, i + 1, width);
    }
    break;
  case 3:
    /* three sort */
    if ((*compar)(SUB(a, i), SUB(a, i + 1)) > 0) {
      SWAP(a, i, i + 1, width);
    }
    /* the first two are now ordered, now order the second two */
    if ((*compar)(SUB(a, i + 2), SUB(a, i + 1)) < 0) {
      SWAP(a, i + 2, i + 1, width);
    }
    /* should the second be moved to the first? */
    if ((*compar)(SUB(a, i + 1), SUB(a, i)) < 0) {
      SWAP(a, i + 1, i, width);
    }
    break;
  default:
    sort_args[1].sa_base          = SUB(a, i);
    sort_args[1].sa_nel           = j;
    sort_args[1].sa_width         = width;
    sort_args[1].sa_compar        = compar;
    if ((thread_count == 0) && (threads_avail > 0) && (i > SLICE_THRESH)) {
      threads_avail--;
      thr_create(0, 0, _quicksort, &sort_args[1], 0, &tid);
      thread_count = 1;
    } else
      _quicksort(&sort_args[1]);
    break;
  }
  if (thread_count) {
    thr_join(tid, 0, 0);
    threads_avail++;
  }
  return 0;
}

void
quicksort(void *a, size_t n, size_t width,
          int (*compar)(const void *, const void *))
{
  static int ncpus = -1;
  sort_args_t sort_args;

  if (ncpus == -1) {
    ncpus = sysconf( _SC_NPROCESSORS_ONLN);

    /* lwp for each cpu */
    if ((ncpus > 1) && (thr_getconcurrency() < ncpus))
      thr_setconcurrency(ncpus);

    /* thread count not to exceed THR_PER_LWP per lwp */
    threads_avail = (ncpus == 1) ? 0 : (ncpus * THR_PER_LWP);
  }
  sort_args.sa_base = a;
  sort_args.sa_nel = n;
  sort_args.sa_width = width;
  sort_args.sa_compar = compar;
  (void) _quicksort(&sort_args);
}
Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top