/* a-wada/qsortlib/ccg/qsortimprv.txt Feb. 16, 2000 */ /* Copyright (c) 2000 Akira Wada */ /* Examples of the improvement of Quick Sort */ /*============================================================================** << Summary of Bench-mark >> *Wed Feb 16 21:53:14 2000 ** * on apricot MS540(i586-166mhz) vine-LINUX-1.1 GCC-2.7.2.3 * average of 10 cases, N = 50,000 element-size = 128 bytes * key1 = string [16] all same chars, key2 = double random unique * pno time ky-cmp rc-trf program & comment * (time=10ms) qs26 241 1440034 454210 qsortpx.c primitive recursion qs21 207 1109021 406404 qsortp.c + increment of pointers after swap qs22 188 952488 420874 qsortpa.c + trace pivot to p.c qs23 182 914657 418964 qsortpb.c + sort_3 (median_3) to p.c qs24 172 825166 451711 qsortr.c + trace pivot + sort3 (median3) to p.c qs25 169 825203 429125 qsortm.c + local stack instead of recursion etc #qs15 165 749011 426920 qsorts.c + median_5 or more, and to prevent from degeneration, etc. optimized fully for system library **============================================================================*/ /* a-wada/qsortlib/ccg/qsortpx.c Nov. 9, 1995 */ /* Copyright (c) 1995 Akira Wada */ /* primitive recursion without increment of pointers after swap */ #include #define COMP(i, j) (*cf)(i, j) #define COPY(i, j) copy (i, j, rl) #define SWAP(i, j) swap (i, j, rl) typedef int (*ftp) (const void *, const void *); void copy (char *, char *, size_t); void swap (char *, char *, size_t); static void qsortprc (char *, char *, size_t, ftp); static char *pvt; void qsort (void *av, size_t rn, size_t rl, ftp cf) { char *l = (char *) av, *r = l + (rn - 1) * rl; pvt = (char*) malloc (rl); qsortprc (l, r, rl, cf); free (pvt);} static void qsortprc (char *l, char *r, size_t rl, ftp cf) { char *i = l, *j = r; if (l < r) { COPY (pvt, l + ((unsigned)((r - l) / rl) / 2) * rl); for ( ; ; ) { while (COMP (i, pvt) < 0) i += rl; while (COMP (pvt, j) < 0) j -= rl; if (i < j) SWAP (i, j); else break;} qsortprc (l, i - rl, rl, cf); qsortprc (j + rl, r, rl, cf);}} /* a-wada/qsortlib/ccg/qsortpx.c end */ /*============================================================================*/ /* a-wada/qsortlib/ccg/qsortp.c Nov. 9, 1995 */ /* Copyright (c) 1995 Akira Wada */ /* primitive recursion */ #include #define COMP(i, j) (*cf)(i, j) #define COPY(i, j) copy (i, j, rl) #define SWAP(i, j) swap (i, j, rl) typedef int (*ftp) (const void *, const void *); void copy (char *, char *, size_t); void swap (char *, char *, size_t); static void qsortprc (char *, char *, size_t, ftp); static char *pvt; void qsort (void *av, size_t rn, size_t rl, ftp cf) { char *l = (char *) av, *r = l + (rn - 1) * rl; pvt = (char*) malloc (rl); qsortprc (l, r, rl, cf); free (pvt);} static void qsortprc (char *l, char *r, size_t rl, ftp cf) { char *i = l, *j = r; if (l < r) { COPY (pvt, l + ((unsigned)((r - l) / rl) / 2) * rl); for ( ; ; ) { while (COMP (i, pvt) < 0) i += rl; while (COMP (pvt, j) < 0) j -= rl; if (i < j) SWAP (i, j); else break; j -= rl, i += rl;} qsortprc (l, i - rl, rl, cf); qsortprc (j + rl, r, rl, cf);}} /* a-wada/qsortlib/ccg/qsortp.c end */ /*============================================================================*/ /* a-wada/qsortlib/ccg/qsortpa.c Nov. 9, 1995 */ /* Copyright (c) 1995 Akira Wada */ /* modified from qsortp.c, tracing pivot */ #define COMP(i, j) (*cf)(i, j) #define SWAP(i, j) swap (i, j, rl) typedef unsigned long size_t; typedef int (*ftp) (const void *, const void *); void swap (char *, char *, size_t); static void qsortprc (char *, char *, size_t, ftp); void qsort (void *av, size_t rn, size_t rl, ftp cf) { char *l = (char *) av, *r = l + (rn - 1) * rl; qsortprc (l, r, rl, cf);} static void qsortprc (char *l, char *r, size_t rl, ftp cf) { char *i, *j, *m; if (l < r) { i = l, j = r, m = l + ((unsigned)((r - l) / rl) / 2) * rl; for ( ; ; ) { while (i < m && COMP (i, m) < 0) i += rl; while (m < j && COMP (m, j) < 0) j -= rl; if (i < j) SWAP (i, j); else break; if (m == j) m = i, j -= rl; else if (i == m) m = j, i += rl; else j -= rl, i += rl;} qsortprc (l, i - rl, rl, cf); qsortprc (j + rl, r, rl, cf);}} /* a-wada/qsortlib/ccg/qsortpa.c end */ /*============================================================================*/ /* a-wada/qsortlib/ccg/qsortpb.c Nov. 9, 1995 */ /* Copyright (c) 1995 Akira Wada */ /* modified from qsortp.c, adding sort-3 (median of 3) */ #include #define COMP(i, j) (*cf)(i, j) #define COPY(i, j) copy (i, j, rl) #define SWAP(i, j) swap (i, j, rl) typedef int (*ftp) (const void *, const void *); void copy (char *, char *, size_t); void swap (char *, char *, size_t); static void qsortprc (char *, char *, size_t, ftp); static char *pvt; void qsort (void *av, size_t rn, size_t rl, ftp cf) { char *l = (char *) av, *r = l + (rn - 1) * rl; pvt = (char*) malloc (rl); qsortprc (l, r, rl, cf); free (pvt);} static void qsortprc (char *l, char *r, size_t rl, ftp cf) { char *i, *j, *m; if (l < r) { i = l, j = r, m = l + ((unsigned)((r - l) / rl) / 2) * rl; if (COMP (m, j) > 0) SWAP (m, j); if (i < m && COMP (i, m) > 0) { SWAP (i, m); if (COMP (m, j) > 0) SWAP (m, j);} if ((i += rl) >= (j -= rl)) return; COPY (pvt, m); for ( ; ; ) { while (COMP (i, pvt) < 0) i += rl; while (COMP (pvt, j) < 0) j -= rl; if (i < j) SWAP (i, j); else break; j -= rl, i += rl;} qsortprc (l, i - rl, rl, cf); qsortprc (j + rl, r, rl, cf);}} /* a-wada/qsortlib/ccg/qsortpb.c end */ /*============================================================================*/ /* a-wada/qsortlib/ccg/qsortr.c Nov. 9, 1995 */ /* Copyright (c) 1995 Akira Wada */ /* modified from qsortp.c */ /* adding sort-3, tracing pivot and avoiding stack overflow */ #define COMP(i, j) (*cf)(i, j) #define SWAP(i, j) swap (i, j, rl) typedef unsigned long size_t; typedef int (*ftp) (const void *, const void *); void swap (char *, char *, size_t); static void qsortprc (char *, char *, size_t, ftp); void qsort (void *av, size_t rn, size_t rl, ftp cf) { char *l = (char *) av, *r = l + (rn - 1) * rl; if (l < r) qsortprc (l, r, rl, cf);} static void qsortprc (char *l, char *r, size_t rl, ftp cf) { char *i, *j, *m; for ( ; ; ) { i = l, j = r, m = l + ((unsigned)((r - l) / rl) / 2) * rl; if (COMP (m, j) > 0) SWAP (m, j); if (i < m && COMP (i, m) > 0) { SWAP (i, m); if (COMP (m, j) > 0) SWAP (m, j);} if ((i += rl) >= (j -= rl)) break; for ( ; ; ) { while (i < m && COMP (i, m) < 0) i += rl; while (m < j && COMP (m, j) < 0) j -= rl; if (i < j) SWAP (i, j); else break; if (m == j) m = i, j -= rl; else if (i == m) m = j, i += rl; else j -= rl, i += rl;} if ((i -= rl) - l <= r - (j += rl)) { if (l < i) qsortprc (l, i, rl, cf); l = j;} else { if (j < r) qsortprc (j, r, rl, cf); r = i;}}} /* a-wada/qsortlib/ccg/qsortr.c end */ /*============================================================================*/ /* a-wada/qsortlib/ccg/qsortm.c Nov. 9, 1995 */ /* Copyright (c) 1995 Akira Wada */ /* modified from qsortr.c */ /* improving 3-sort a little to reduce the times of transfer & */ /* using local stack to eliminate recursive function calls */ #define COMP(i, j) (*cf)(i, j) #define SWAP(i, j) swap (i, j, rl) #define ROTATE(i, j, k) rotate (i, j, k, rl) typedef unsigned long size_t; typedef int (*ftp) (const void *, const void *); void swap (char *, char *, size_t); void rotate (char *, char *, char *, size_t); void qsort (void *av, size_t rn, size_t rl, ftp cf) { char *l = (char *) av, *r = l + (rn - 1) * rl, *i, *j, *m, *s[sizeof (int) * 16], **p = s; if (l < r) for ( ; ; ) { m = l + ((unsigned)((r - l) / rl) / 2) * rl; if (COMP (m, r) <= 0) { if (l < m && COMP (l, m) > 0) if (COMP (l, r) <= 0) SWAP (l, m); else ROTATE (m, r, l);} else if (l >= m || COMP (l, m) > 0) SWAP (l, r); else if (COMP (l, r) <= 0) SWAP (m, r); else ROTATE (m, l, r); if ((i = l + rl) < (j = r - rl)) { for ( ; ; ) { while (i < m && COMP (i, m) < 0) i += rl; while (m < j && COMP (m, j) < 0) j -= rl; if (i < j) SWAP (i, j); else break; if (m == j) m = i, j -= rl; else if (i == m) m = j, i += rl; else j -= rl, i += rl;} if ((i -= rl) - l <= r - (j += rl)) { if (l < i) *(p++) = j, *(p++) = r, r = i; else l = j;} else { if (j < r) *(p++) = l, *(p++) = i, l = j; else r = i;}} else { if (s < p) r = *(--p), l = *(--p); else break;}}} /* a-wada/qsortlib/ccg/qsortm.c end */ /*============================================================================** * /win95-c/a-wada/linux/ccg/qsortcn5 on apricot MS540 p-166 vine-LINUX-1.1 GCC-2.7.2.3 * Wed Feb 16 21:45:37 2000 * obj1 = struct {int, char*, double, int, char[108]}, lng = 128 * key1 = string [16] all-same-chars, word boundary * key2 = double random unique * mode 0, 1, 2 or 3 =: 3 * sort names * 0. qsort.sys * 1. qsort-S551rvs.c 2. qsorts54impv.c 3. qsort-Emacs.c 4. qsort-Postgrs.c 5. qsort-FreeBsd.c * 6. qsort-Darcy.c 7. qsort-Kawamr6.c 8. qsort-Kawamr7.c 9. qsortad.c 10. qsortax.c * 11. qsorta.c 12. *qsortbz.c 13. *qsortbx.c 14. qsortb.c 15. qsorts.c * 16. qsortu.s 17. qsortc.c 18. qsortv.c 19. *qsortw.s 20. *qsortd.c * 21. qsortp.c 22. qsortpa.c 23. qsortpb.c 24. qsortr.c 25. qsortm.c * 26. qsortx.c 27. qsort-Stubbs.c 28. qsort-Intro.c 29. qsort-McCghn.c 30. *qsort-Wilt.c ng-seq * 31. qsort-Morse.c 32. qsort-GNU.c 33. qsort-Heap.c 34. qsort-Comb.c 35. qsort-Mrg.c * 36. shell-rs.c 37. *qsort-msDos.c 38. qsort-Dviware.c 39. radixspi-ar.c 40. qsort-Plauger.c * 41. qsort-MSVCP40.c * Select 5 sort_names of 1 - 41 := * qs21 = qsortp.c qs22 = qsortpa.c qs23 = qsortpb.c qs24 = qsortr.c qs25 = qsortm.c * n =: 50000 ncase =: 10 seed =: 8571782 ds =: 9753137 pc =: 2 * wdbd = 1 lmin = 29 lmax = 33 nsch = 1 bsch = x61 rmd = 0 cmpf = 1 * seed =: 8571782 ds =: 9753137 t=sys qs21 qs22 qs23 qs24 qs25 c=sys qs21 qs22 qs23 qs24 qs25 m=qs21 qs22 qs23 qs24 qs25 167 209 189 182 170 168 813643 1120902 953539 912858 813393 813643 405607 421964 417485 454016 431315 167 203 188 181 169 168 805969 1080293 951144 895653 805935 805969 408891 423076 421023 454196 431486 169 209 183 183 171 169 820226 1116451 918295 919531 820189 820226 406371 421304 418016 452640 430008 172 209 189 185 175 171 839203 1122994 950962 927986 839161 839203 402812 419732 418079 447172 424813 173 206 192 187 176 172 839203 1098624 972418 938738 845114 839203 405391 424128 416337 452408 429788 174 225 205 187 177 173 859068 1218427 1061388 947093 859030 859068 400739 417088 415214 451784 429195 169 202 183 180 171 170 817871 1074582 912344 897850 817838 817871 408775 423620 421259 448772 426333 166 205 188 180 169 166 802351 1089062 951029 897502 802315 802351 409705 415974 421492 447814 425423 169 208 190 181 171 167 815083 1104034 958513 901741 815044 815083 406777 421536 421100 453008 430358 170 201 180 182 174 171 833680 1064850 895255 907627 833643 833680 408979 420320 419644 455308 432543 x 174 225 205 187 177 173 859068 1218427 1061388 947093 859030 859068 409705 424128 421492 455308 432543 a 169 207 188 182 172 169 825203 1109021 952488 914657 825166 825203 406404 420874 418964 451711 429125 n 166 201 180 180 169 166 802351 1064850 895255 895653 802315 802351 400739 415974 415214 447172 424813 * sys qs21 qs22 qs23 qs24 qs25 * avr_t = 169 207 188 182 172 169 * c = 825203 1109021 952488 914657 825166 825203 * m = 406404 420874 418964 451711 429125 * c + m = 1515425 1373362 1333621 1276877 1254328 * qs21 = qsortp.c qs22 = qsortpa.c qs23 = qsortpb.c qs24 = qsortr.c qs25 = qsortm.c * mode 0, 1, 2 or 3 =: 3 * sort names * 0. qsort.sys * 1. qsort-S551rvs.c 2. qsorts54impv.c 3. qsort-Emacs.c 4. qsort-Postgrs.c 5. qsort-FreeBsd.c * 6. qsort-Darcy.c 7. qsort-Kawamr6.c 8. qsort-Kawamr7.c 9. qsortad.c 10. qsortax.c * 11. qsorta.c 12. *qsortbz.c 13. *qsortbx.c 14. qsortb.c 15. qsorts.c * 16. qsortu.s 17. qsortc.c 18. qsortv.c 19. *qsortw.s 20. *qsortd.c * 21. qsortp.c 22. qsortpa.c 23. qsortpb.c 24. qsortr.c 25. qsortm.c * 26. qsortx.c 27. qsort-Stubbs.c 28. qsort-Intro.c 29. qsort-McCghn.c 30. *qsort-Wilt.c ng-seq * 31. qsort-Morse.c 32. qsort-GNU.c 33. qsort-Heap.c 34. qsort-Comb.c 35. qsort-Mrg.c * 36. shell-rs.c 37. *qsort-msDos.c 38. qsort-Dviware.c 39. radixspi-ar.c 40. qsort-Plauger.c * 41. qsort-MSVCP40.c * Select 5 sort_names of 1 - 41 := * qs26 = qsortx.c qs15 = qsorts.c qs14 = qsortb.c * n =: 50000 ncase =: 10 seed =: 8571782 ds =: 9753137 pc =: 2 * wdbd = 1 lmin = 29 lmax = 33 nsch = 1 bsch = x61 rmd = 0 cmpf = 1 * seed =: 8571782 ds =: 9753137 t=sys qs26 qs15 qs14 c=sys qs26 qs15 qs14 m=qs26 qs15 qs14 168 243 165 164 813643 1442089 749389 749389 455257 427806 427806 167 241 166 165 805969 1440878 751827 751827 456405 428444 428444 169 237 165 164 820226 1406421 748400 748400 454715 427396 427396 172 241 164 163 839203 1437356 745460 745460 453063 424208 424208 172 244 164 163 839203 1463330 747832 747832 457520 423729 423729 175 258 165 164 859068 1545080 748733 748733 450390 428101 428101 169 235 164 163 817871 1402574 743941 743941 456925 423188 423188 167 240 165 164 802351 1433725 751304 751304 449335 426810 426810 169 243 166 165 815083 1446679 753004 753004 454851 430137 430137 171 233 166 165 833680 1382213 750223 750223 453639 429386 429386 x 175 258 166 165 859068 1545080 753004 753004 457520 430137 430137 a 169 241 165 164 825203 1440034 749011 749011 454210 426920 426920 n 167 233 164 163 802351 1382213 743941 743941 449335 423188 423188 * sys qs26 qs15 qs14 * avr_t = 169 241 165 164 * c = 825203 1440034 749011 749011 * m = 454210 426920 426920 * c + m = 1894244 1175931 1175931 * qs26 = qsortx.c qs15 = qsorts.c qs14 = qsortb.c * mode 0, 1, 2 or 3 =: 9 << Summary of Bench-mark >> * pno time ky-cmp rc-trf program & comment * sys 169 825203 0 qsort.sys overridden by qsortm.c qs26 241 1440034 454210 qsortx.c testing sortprogram qs21 207 1109021 406404 qsortp.c primitive recursion qs22 188 952488 420874 qsortpa.c adding trace of pivot to p.c qs23 182 914657 418964 qsortpb.c adding sort-3 (median of 3) to p.c qs24 172 825166 451711 qsortr.c sort-3 & trace of pivot qs25 169 825203 429125 qsortm.c local stack instead of recursion qs14 164 749011 426920 qsortb.c compatible, word-swap, no stability qs15 165 749011 426920 qsorts.c (optimized in C from qsortb.c) * /win95-c/a-wada/linux/ccg/qsortcn5 end * Wed Feb 16 21:53:14 2000 **============================================================================*/ /* a-wada/qsortlib/ccg/qsortimprv.txt end */