Улучшение быстрого сортировки

Question

Если возможно, как можно улучшить следующую быструю сортировку (качество работы). Какие-либо предложения?

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 

Answer 1

Алгоритм быстрой сортировки легко распараллелен. Если у вас несколько ядер, с которыми можно работать, вы могли бы немного ускориться.В зависимости от того, насколько велико ваш набор данных, он может легко обеспечить вам более высокую скорость, чем любая другая оптимизация. Однако, если у вас есть только один процессор или относительно небольшой набор данных, скорость не будет большой.

Я мог бы разработать больше, если это возможно.

Answer 2

wikipedia article on quicksort имеет кучу идей.

Answer 3

1. Выберите лучший стержень: напр. в медианной из трех вы выбираете 3 (случайных) элемента и выбираете опорный элемент в качестве медианного элемента
2. Когда длина (a []) < M (на практике выберите M = 9) прекратите сортировку. После завершения qsort() примените сортировку вставки, которая займет приблизительно M * N = O (N). Это позволяет избежать множества вызовов функций, близких к листу дерева рекурсии divide-et-impera.

Answer 4

Первое предложение было бы: заменить один из рекурсивных вызовов на итерацию. И я имею в виду настоящую итерацию, а не реализованный вручную стек для рекурсии. То есть вместо двух «новых» звонков на quick от quick, «переработайте» ваш текущий, позвоните в quick, чтобы обработать одну ветвь рекурсии и вызывать quick рекурсивно для обработки другой ветки.

Теперь, если вы убедитесь, что вы всегда сделать реальный рекурсивный вызов для раздела короче (и использовать итерацию для более одного), это гарантирует, что глубина рекурсии никогда не превысит log N даже в самом худшем случае , то есть независимо от того, насколько хорошо вы выбираете медиана.

Все это реализовано в алгоритме qsort, который поставляется со стандартной библиотекой GCC. Взгляните на источник, это должно быть полезно.

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

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

Это всего лишь набросок идеи, конечно. Не испытано. Опять же, взгляните на реализацию GCC для той же идеи. Они также заменяют оставшийся рекурсивный вызов «ручной» рекурсией, но на самом деле это не обязательно.

Answer 5

Сортировка небольших блоков (< 5 элементов) с помощью алгоритма без петли может повысить производительность. Я нашел только один пример, как написать алгоритм сортировки loopless 5 элементов: http://wiki.tcl.tk/4118

Идея может быть использована для генерации алгоритмов сортировки для loopless 2,3,4,5 элементов в C.

EDIT: я попробовал это на одном наборе данных, и я измерил 87% времени работы по сравнению с кодом в вопросе. Использование сортировки вставки на < 20 блоков привели к тому же набору данных на 92%. Это измерение не является репрезентативным, но может показать, что это способ улучшить код быстрой сортировки.

EDIT: этот пример кода выписать loopless функции сортировки для 2-6 элементов:

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

сгенерированный код 3718 линии длиной:

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

Answer 6

Попробуйте другой алгоритм сортировки.

В зависимости от ваших данных вы можете обменять память на скорость.

Согласно Википедии

• Quick sort имеет лучший случай O (N журнал N) производительность и O (1) пространство
• Merge sort имеет неподвижную O (п § п) и O (n) пробел
• Radix sort имеет фиксированный O (n. < количество разрядов >) производительность и O (n. < количество цифр >) пространство

---

Редактировать

Видимо ваши данные целые числа. С 2.5M целыми числами в диапазоне [0, 0x0fffffff] моя реализация radix-sort примерно в 4 раза быстрее, чем ваша реализация 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; 
} 

Answer 7

Если это не только для изучения использования qsort из stdlib.h

Answer 8

1. Вы можете устранить recuriosn над головой с помощью QuickSort с Явным 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. Вы можете использовать лучшую технику выбора поворота, такую ​​как:

   1. медиана 3
   2. медиана медиан
   3. случайного поворота

Answer 9

Per код, при сортировке длина составляет 10, самый глубокий стек выглядит

#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 

Помимо самого алгоритма, если мы рассмотрим поведение системы, например, действия стека, то el кроме обычных расходов на стеки вызовов (push/pop), можно понизить производительность по лотам, например. переключение контекста, если многозадачная система, вы знаете, что большинство ОС являются многозадачными, а глубже стека выше затраты на коммутацию, плюс промаху кеша или границу cachline.

Я верю в этот случай, если длина станет больше, вы проиграете по сравнению с некоторыми другими сортирующими альго.

, например, при длине до 40, стек может выглядеть так (может больше записей, чем показано ниже):

#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 

слишком глубокий стек.

Функциональная вставка также полезна, но она увеличивает размер кода конечного исполняемого файла. Я согласен с @Swiss, параллельное программирование может вам помочь.

Answer 10

Первое, что нужно сделать, это сравнить его. И сравните его со стандартным qsort, и против C++ std :: sort и std :: stable_sort.

Ваши результаты, если ваш набор данных будет достаточно большим, покажет, что std :: sort превосходит qsort во всех случаях за исключением тех, где std :: stable_sort превосходит. Это связано с тем, что std :: sort шаблонизирован, и поэтому сравнение может быть включено.

Ваш код в строках сравнения, потому что его не общий. Если ваш код медленнее qsort, у вас есть проблема прямо там.

Более быстрая сортировка - это сортировать детали параллельно, например. openmp, а затем объединить их вместе.

Answer 11

Скопировано из моего ответа на вопрос ответа.

Редактировать: Это сообщение предполагает, что вы уже делаете очевидные вещи, например, воспользуйтесь хвостовой рекурсией, чтобы избавиться от ненужных накладных расходов.

Людям нравится критиковать быстродействующую сортировку за плохую работу с определенными входами, особенно, когда пользователь имеет контроль над входом. Следующий подход приводит к сопоставлению результатов по средней точке, но ожидаемая сложность экспоненциально подходит к O (n log n), поскольку список растет в размере. По моему опыту он значительно превосходит лучший выбор из-за гораздо меньших накладных расходов в большинстве случаев. Он должен выполнять равномерно с выбором средней точки для «ожидаемых» входов, но не уязвим для плохих входных данных.

• Инициализировать quicksort случайным положительным целым I. Это значение будет использоваться в процессе сортировки (не нужно генерировать несколько номеров).
• Pivot выбран как I mod SectionSize.

Для дополнительной производительности вы всегда должны переключать свою сортировку quicksort на shell для «маленьких» сегментов списка. Я видел длины от 15-100, выбранных в качестве отсечки.

Answer 12

многопоточность?

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

Answer 13

полностью немой ответ, но ... скомпилируйте свой код в режиме деблокирования и включите оптимизацию!

Answer 14

В настоящее время наиболее передовая быстрая сортировка широко используется реализован в Java-х DualPivotQuicksort.java Таким образом, вы можете просто следовать этому подходу, и вы увидите хороший прирост производительности:

• Использование Вносимых сортировок для небольших массивов (47 этого число используется в Java)
• использования что двойной шарнирной сортировка выбора 2-й и 4-е элементы 5 в качестве двух шарниров
• Рассмотрите возможность использования массивов для сортировки слияния с пробегами отсортированных чисел

Или, если вы хотите добавить немного сложнее, введите код 3-pivot quicksort.