/* a-wada/qsortlib/ccg/qsortbs.txt Nov. 17, 2006 */ /* Copyright (c) 2006 Akira Wada */ /* *** Algorithm of Quick-Sort (QSORTBASE) *** Partitioning Method used scince I implemented a qsort at first on 1997, refering to qsort-Emacs.c in of SunOS 5.4, was changed to the way new, ie. when scanning encounters pivot itself, skip over it without comparison instead of stopping and swapping, and later move pivot to the final position, to reduce total exchanges without large increasing of compares, suggested from the newest revision of qsort.c in OPENSOLARIS, http://src.opensolaris.org/source/raw/onnv/onnv-gate /usr/src/common/util/qsort.c Jan 06, 2006. (01-04) Set pointers to the left- and right-end of the current partition to the both ends of the array to be sorted, prepare and initialize the local stack for pointers, and other housekeepings if required. (05-06) Get partition-size of the current partition and pointer to the middle from both ends, set left and right scan pointers to each end, and reset the threshold for selecting median and adjust it by small value. (08-09) If middle and right are in order and (p-size is 2, or left and middle in order), no swap is required then go to (14). (10) If middle and right in order, and left and middle out of order, find the minimum of left and from right to rightend, and if it is left, swap middle with left, else rotate so that minimum to middle, left to the place where minmum existed, and middle to left, then go to (14). (11-12) If middle and right out and (p-size is 2, or left and middle out), swap left with right, and go to (14). (13) If middle and right out, and left and middle in order, find the maximum of right and from leftend to left, and if it is right, swap middle with right, else rotate so that maximum to middle, right to where maxmum existed and middle to right. (14-15) At the 1'st pass of (08-13), leftend, middle and rightend have been sorted i.e. the median of the 3 brought into middle and the 1'st step of partitioning done. Then increment pointers toward inside, and if p-size is greater than threshold, multiply threshold by a value (usually = 2) and iterate from (08). At the 2'nd iteration and the later, based on the result of the previous iteration, median of the 5, (middle, leftend and rightend and added one pair of the next elements inside of each end) and the more (added one more pair of the next inside), would be brought into middle, and partitioning of them by middle done. Otherwise i.e if p-size is not greater than threshold, break the loop. (16) If p-size is smaller than 4, the positions of the elements have been determined, then go to (37), else continue partitioning (17-29) by middle as pivot, gathering equal-keys to left end. (17) Set the pointer to equal-key-group to left end. (18-22) Scan from left end toward inside, and when it encounters pivot itself, skip over it without cmparison, and stop at the element out of order as compared with pivot. The elements which have equal key as pivot would be gathered to left end by exchange, and so on. (23-26) Scan from right end toward inside, and when it encounters pivot itself, skip over it without cmparison, and stop at the element equal to or out of order as compared with pivot. (27) If both scan have meeted or crossed over eachother stop partitioning by pivot then go to (30). (28) If right does not have equal key, swap left with right. Else rotete so that right to inside of equal-key-group, left to right and the guy in the position to where equal-key was brought, to left, and so on. (29) Advance pointers toward inside to scan again from next of both sides, and go back to (18). (30) Find the final position of pivot left almost untouched, and move it by exchange with the element in order. (31) Set pointers to inside edge of each subpartition and if equal keys have been gathered to left end move them to where to be. (32-36) Compare the size of both subpartitions, and when the smaller is less than 2, position of the element has been determined, then to process the larger recursively, go back to (05), but when the smaller not less than 2, push down pointers to both ends of the larger, onto stack for later process, and go back to (05) to process the smaller at first. (37) If stack is not empty, pop up pointers to both ends and go back to (05) to process the partition. If stack is empty the Sorting is complete. (38) Cleanup if necessary. * for prevention from the degeneration caused by peculiar input * DFDGN; Define the counter for the symptoms of degeneration, the interval of samples distributed uniformly, and the already sorted-flag, etc. CKDGN; At the end of each partitioning for the partition not less than DGT, if the size of the smaller subpartition is less than p-size / DGV, assume the symptom of degeneration and count up the counter. AVDGN; For the partition greater than MDT, according to dgn, change the method to select samples for the median. (number of samples nearly = 2 * (log2 (p-size)) - 3, except stage-1) .normal; 0 == dgn <= DGM : middle, both ends and close to both ends .stage-1; DGM < dgn <= DGS : no median (middle for pivot) .stage-2; DGS < dgn <= DGU : samples distributed uniformly .stage-3; DGU < dgn : samples at random SETCS; Set the already sorted-flag on, before selecting median. RSTCS; During selecting median, if any pair of samples are out of order, reset the sorted-flag off. CKSRT; Before main partitioning if the sorted-flag kept on, and p-size greater than MDT, check the partition sorted completely or half, and if so, set pointer to bypass the partitioning or to reduce the comparisons. */ /* *** About these Implementations *** The algorithms, what to do, have been argued almost in the documents 1 and 2 referred to. It is suggested in Knuth's Vol 3, page 123, referring to Singleton and Frazer & McKellar, to select median of the 3, and of the sample consisting of P = 2 * K + 1 elements, when size of the parti- tion S >= 2 ** (a + b * (K - 2)) + c, for K >= 2, (although the number of sample elements and threshold are different from the original). The features of these implementations may be compactness and efficiency, that is to reduce the total number of key-comparisons near to that of the merge-sort without large working spaces nor large increase of the transfers of the elements, by following (1), (2), (3) and (4). (1) Sorting the 3 (leftend, middle and rightend) works for two purposes, the one is sorting finally the subpartition smaller than 4, instead of insertion-sort, either for each small subpartition when created or as a single pass at the end process, and the another is, for the partition not smaller than 4, selecting median of the 3, bringing it to middle as pivot for partitioning and doing the 1'st step of partitioning. For the partition larger than a threshold, based on the result of above sort-3, median of the 5 is selected, and if it is not middle, it is brought into middle by exchange. These advance one step of partitioning. If the size is still larger than the threshold which has been multiplied by 2 ** b, median of the 7 is selected, and partitioning done. Median of the 9, the 11,...and so on. When the coefficients a = 4, b = 1 and c = 4, according to the size of partition S, median of the P elements, would be selected. <= S < : 4, 20, 36, 68, 132, 260, 516, 1028, 2052, 4100, 8196, 16388,.... P : 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25,.. (these coefficients i.e. MDT = 16, MDM = 2, MDA = 2 were decided to make the times of key-comparisons minimum, for 10 cases sorting the arrays of 10,000 items with randomized keys.) (2) To avoid the degeneration caused by many equal sort-keys, or rather to take advantage of such a situation, at main partitioning, gathering the elements which have same sort-key as pivot close to the pivot, but for stability, i.e. to preserve the initial order of them, a unique-key e.g. numbering each element or pointer itself for array of pointers, should be used at the actual usage. (3) For peculiar input e.g. sorted partially in order or in reversed order, [for examples: int a[10000] = {7519, 7520, 7521, ... , 9997, 9998, 9999, 5033, 5034, 5035, ... , 7516, 7517, 7518, 2442, 2443, 2444, ... , 5030, 5031, 5032, 0, 1, 2, 3, 4, 5, ... , 2439, 2440, 2441}; or int b[10000] = {0, 9999, 9998, 9997, ... , 5, 4, 3, 2, 1}; or int c[10000] = {9999, 9997, 9995, ... , 5, 3, 1, 0, 2, 4, ..., 9994, 9996, 9998}; or int c[10001] = {0, 5000, 2, 5002, ... , 4996, 9996, 4998, 9998, 1, 3, 5, 7, 9, 11, ... , 9995, 9997, 9999, 10000}; etc.,] selecting median of the samples congregated near to both ends would make the degenerations ready to occur, then at the end of each partitioning, detecting the degeneration and if symptomatic, stopping to select median for a while, changing the interval of samples to distribute uniformly or sampling at random, by stages to mess up the peculiar or malicious arrangement. For the artificial arrangement, not always random, in the many practical applications, some preventions might be indispensable. (4) Using middle element as pivot, tracing the travels of pivot by pointer, using an explicit local stack to eliminate recursive function calls, and processing the smaller subpartition at first, etc. */ /* Using middle element instead of left- or right-end as pivot could avoid the worst case behavior for an array already sorted, where the size of subpartition is reduced only one by one at each partitioning. But even if middle is used as pivot, such arrangements might exist, although the probability is very small. Then the purpose to select median for pivot is to make the probability still smaller by equalizing the size of sub- partitions as possible, and as the result to reduce the total number of key comparisons. The reduction of key-comparisons by selecting median, was 24,994 (from 150,536 to 125,542 about 17%), as compare against qsort in stdlib.h of a system, at an average of 10 cases of 10,000 items, with randomized keys. An average sorting time was reduced at a smaller rate than above, only by reducing comparisons, but was reduced at a larger rate, by swapping word-wise instead of byte-wise, or by sorting the array of pointers and arranging the actual elements using the sorted pointers. Selecting median may be regarded as very cheap insurance dues, for some particularly queer arrangements of elements in the initial arrays. */ /* The following have been referred to, 1. R.Sedgewick, Algorithms in C++, & the edition translated into japanese, 2. D.E.Knuth, The Art of Computer Programming, Vol.3 (the 2'nd printing), 3. ftp://ring.aist.go.jp/pub/TeX/CTAN/indexing/makeindex/src/qsort.c May 26, 1993, 4. ftp://ftp.sra.co.jp/pub/cmd/postgres/6.2.1 /postgresql-6.2.1/src/backend/lib/qsort.c Oct 20, 1997, 5. ftp://ftp.jp.freebsd.org/pub/FreeBSD/FreeBSD-current /src/sys/libkern/qsort.c Feb 22, 1997, 6. ftp://ftp.nizkor.vex.net/local/src/darcy/common/qsort.c Jan 22, 1997, 7. http://www.tokuyama.ac.jp/home/~kawamura/ qs6.c & qs7.c Nov 27, 1997, 29. ftp://ftp.groggs.group.cam.ac.uk/pub/software/qsort.c-1.12 May 6, 1998, 32. ftp://ftp.linux.org.uk/pub/linux/libc/libc-5.4.44.tar.gz Feb 2, 1998, (32) /libc/stdlib/_quicksort.c (961005) (35) /libc/stdlib/qsort.c (950218) 39. http://www.cubic.org/~submissive/sourcerer/download/radix_ar.c May 25, 1997, 47. http://src.opensolaris.org/source/raw/onnv/onnv-gate/usr /src/common/util/qsort.c Jan 06, 2006, and many other ftps and https. */ /* *** << Summary of Bench-mark >> *** * average of 10 cases, N = 10,000 element-size = 32(A), 128(B) bytes * key1 = string [16] all same chars, key2 = double random unique time (10msec) *pno A B ky-cmp el-trf program & comment sys 46 84 150536 - qsort.stdlib.h of the system (SunOS 5.4 ss20-40) qs-3 46 84 150536 73809 qsort-Emacs.c (e) ftp 3.= SunOS 5.4 != 5.5.1 qs-4 43 78 142661 73813 qsort-Postgrs.c (g) ftp 4. qs-5 35 49 135937 74919 qsort-FreeBsd.c (f) ftp 5. qs-6 34 45 140823 75345 qsort-Darcy.c (h) ftp 6. qs-7 33 45 132017 64184 qsort-Kawamr6.c (k6) http 7. qs-8 33 46 134702 70700 qsort-Kawamr7.c (k7) http 7. qs11 28 43 125542 74546 qsorta.c tailor-made, comp & swap inline qs14 31 45 125542 74546 qsortb.c compatible, word-swap, anti-dgn qs15 31 45 125542 72474 qsorts.c (optimized in C from qsortb.c for sys) qs17 35 38 125542 10007 qsortc.c compatible(ptr-sort) stablty, anti-dgn qs18 33 36 125542 10007 qsortv.c (optimized in C from qsortc.c) qs20 30 33 125542 10007 qsortd.c tailor-made(ptr-sort) stblty, anti-dgn qs22 24 27 (125511) (10007) qsortds.s (optimized in Asm from qsortd.c) */ << Summary of Bench-mark >> * on apricot MS540 p-166 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 (10msec) sys 466 718168 - qsort.sys stdlib.h of the system qs-3 259 874687 435686 qsort-Emacs.c (e) ftp 3.= SunOS 5.4 != 5.5.1 qs-4 250 835126 435713 qsort-Postgrs.c (g) ftp 4. qs-5 178 810289 431195 qsort-FreeBsd.c (f) ftp 5. qs-6 178 848691 431422 qsort-Darcy.c (h) ftp 6. qs-7 163 785608 377548 qsort-Kawamura6.c(k6) http 7. qs-8 168 804769 409642 qsort-Kawamura7.c(k7) http 7. qs29 192 857102 468358 qsort-McCaughan.c(k5) ftp 29. qs32 285 914257 412012 qsort-GNU.c (i) ftp 32. Quick Sort in gnu qs35 469 718168 1491506 qsort-Mrg.c (j) ftp 32. Merge Sort in gnu qs11 160 749011 426920 qsorta.c tailor-made, comp inline qs14 165 749011 426920 qsortb.c compatible, word-swap, no stability qs15 164 749011 426920 qsorts.c (optimized in C from qsortb.c) qs16 159 749011 (426920) qsortu.s (optimized in Asm from qsorts.c) qs17 138 749011 50008 qsortc.c compatible(ptr-sort) stablty, anti-dgn << Summary of Bench-mark >> * on apricot MS540 p-166 vine-LINUX-1.1 GCC-2.7.2.3 * for an array of pointers to struct with an unsigned integer key * average of 10 cases, N = 100,000 element-size = 4 bytes * key1 = unsigned integer random unique * pno time ky-cmp rc-trf program & comment * sys 88 1536405 - qsort.sys stdlib.h of the system qs-3 107 1890839 929961 qsort-Emacs.c (e) ftp 3.= SunOS 5.4 != 5.5.1 qs-4 99 1811649 930011 qsort-Postgrs.c (g) ftp 4. qs-5 88 1723265 911248 qsort-FreeBsd.c (f) ftp 5. qs-6 89 1813021 910092 qsort-Darcy.c (h) ftp 6. qs-7 87 1686461 802240 qsort-Kawamr6.c (k6) http 7. qs-8 88 1705534 868753 qsort-Kawamr7.c (k7) http 7. qs29 80 1821043 1062453 qsort-McCaughan.c(k5) ftp 29. qs32 96 1912400 875876 qsort-GNU.c (i) ftp 32. Quick Sort in gnu qs35 95 1536405 3182942 qsort-Mrg.c (j) ftp 32. Merge Sort in gnu qs11 61 1600582 911771 qsortapi.c tailor-made, comp & swap inline qs14 89 1600582 911771 qsortb.c compatible, word-swap, no stability qs15 79 1600582 911771 qsorts.c (optimized in C from qsortb.c) qs16 72 1600582 - qsortu.s (optimized in Asm from qsorts.c) qs39 28 400000 200000 radixspi-ar.c (k8) http 39. Radix Sort modified /* a-wada/qsortlib/ccg/qsortbs.txt end */