1 /* 2 * Copyright (c) 2006-2018, RT-Thread Development Team 3 * 4 * SPDX-License-Identifier: Apache-2.0 5 * 6 * Change Logs: 7 * Date Author Notes 8 */ 9 #include <sys/types.h> 10 #include <stdlib.h> 11 12 static void exch(char* base,size_t size,size_t a,size_t b) { 13 char* x=base+a*size; 14 char* y=base+b*size; 15 while (size) { 16 char z=*x; 17 *x=*y; 18 *y=z; 19 --size; ++x; ++y; 20 } 21 } 22 23 /* Quicksort with 3-way partitioning, ala Sedgewick */ 24 /* Blame him for the scary variable names */ 25 /* http://www.cs.princeton.edu/~rs/talks/QuicksortIsOptimal.pdf */ 26 static void quicksort(char* base,size_t size,ssize_t l,ssize_t r, 27 int (*compar)(const void*,const void*)) { 28 ssize_t i=l-1, j=r, p=l-1, q=r, k; 29 char* v=base+r*size; 30 if (r<=l) return; 31 for (;;) { 32 while (++i != r && compar(base+i*size,v)<0) ; 33 while (compar(v,base+(--j)*size)<0) if (j == l) break; 34 if (i >= j) break; 35 exch(base,size,i,j); 36 if (compar(base+i*size,v)==0) exch(base,size,++p,i); 37 if (compar(v,base+j*size)==0) exch(base,size,j,--q); 38 } 39 exch(base,size,i,r); j = i-1; ++i; 40 for (k=l; k<p; k++, j--) exch(base,size,k,j); 41 for (k=r-1; k>q; k--, i++) exch(base,size,i,k); 42 quicksort(base,size,l,j,compar); 43 quicksort(base,size,i,r,compar); 44 } 45 46 void qsort(void* base,size_t nmemb,size_t size,int (*compar)(const void*,const void*)) { 47 /* check for integer overflows */ 48 if (nmemb >= (((size_t)-1)>>1) || 49 size >= (((size_t)-1)>>1)) return; 50 if (nmemb>1) 51 quicksort(base,size,0,nmemb-1,compar); 52 } 53