From: Kbwms Message-ID: <63bde56d.3547cc6c@aol.com> Date: Wed, 29 Apr 1998 20:57:15 EDT To: eliz AT is DOT elta DOT co DOT il (Eli Zaretskii) Cc: djgpp AT delorie DOT com Mime-Version: 1.0 Subject: GNU qsort() Content-type: text/plain; charset=US-ASCII Content-transfer-encoding: 7bit Precedence: bulk eliz AT is DOT elta DOT co DOT il (Eli Zaretskii) Dear Eli Zaretskii, It occurred to me this evening that the sort statistics for fqsort on the same sort targets that I sent for GNU qsort() might be of interest. Data from separate runs is appended. Here is a recap: Items Comparisons Exchanges ----- ----------- --------- 10000 15005 2503 20000 30005 5003 50000 75005 12503 100000 150005 25003 (0.109890 Seconds) Unfortunately, the function ran so quickly that individual timing numbers were not available except on the last one. As you can see, the numbers of comparisons and exchanges both grow linearly as a function of the number of items. This behavior is linear O(n) for this sort target instead of the theoretical O(n*log2(n)). The numbers for this last item for GNU qsort() are: Items Comparisons Exchanges ----- ----------- --------- 100000 2500329228 50717 (843.626374 Seconds) If you would like a zip file of my entire test suite with makefile, I would be delighted to send it to you. An article describing this suite appeared in "Testing Sort Functions," C/C++ Users Journal, vol. 13, no. 07, July 1995. K.B. Williams ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Generating Targets in [10000 (10000) 10000] Sort Function is FatQsort(Median Pvt) PlotTimer Option is FALSE Items Comparisons Exchanges Code/Target I.D. 10000 NO-SORT NO-SORT (R) Random-Uniform NO-SORT NO-SORT (S) Already-Sorted NO-SORT NO-SORT (V) Reverse-Sorted NO-SORT NO-SORT (H) Reverse-Sorted-by-Halves NO-SORT NO-SORT (F) First-Item-Out-of-Order NO-SORT NO-SORT (T) Every-Third-Item-Inverted NO-SORT NO-SORT (Q) All-Items-Equal NO-SORT NO-SORT (E) Every-Eighth-Item-Different 15005 2503 (A) Alternating-Pairs NO-SORT NO-SORT (B) Bore-Sight-Simulation Suite Stats: 10000 Items/Target, 0.000000 Seconds 15005 Comparisons, 2503 Exchanges Total Sort Time: 0 Hrs, 0 Mins, 0.5 Secs Generating Targets in [20000 (20000) 20000] Sort Function is FatQsort(Median Pvt) PlotTimer Option is FALSE Items Comparisons Exchanges Code/Target I.D. 20000 NO-SORT NO-SORT (R) Random-Uniform NO-SORT NO-SORT (S) Already-Sorted NO-SORT NO-SORT (V) Reverse-Sorted NO-SORT NO-SORT (H) Reverse-Sorted-by-Halves NO-SORT NO-SORT (F) First-Item-Out-of-Order NO-SORT NO-SORT (T) Every-Third-Item-Inverted NO-SORT NO-SORT (Q) All-Items-Equal NO-SORT NO-SORT (E) Every-Eighth-Item-Different 30005 5003 (A) Alternating-Pairs NO-SORT NO-SORT (B) Bore-Sight-Simulation Suite Stats: 20000 Items/Target, 0.000000 Seconds 30005 Comparisons, 5003 Exchanges Total Sort Time: 0 Hrs, 0 Mins, 0.5 Secs Generating Targets in [50000 (50000) 50000] Sort Function is FatQsort(Median Pvt) PlotTimer Option is FALSE Items Comparisons Exchanges Code/Target I.D. 50000 NO-SORT NO-SORT (R) Random-Uniform NO-SORT NO-SORT (S) Already-Sorted NO-SORT NO-SORT (V) Reverse-Sorted NO-SORT NO-SORT (H) Reverse-Sorted-by-Halves NO-SORT NO-SORT (F) First-Item-Out-of-Order NO-SORT NO-SORT (T) Every-Third-Item-Inverted NO-SORT NO-SORT (Q) All-Items-Equal NO-SORT NO-SORT (E) Every-Eighth-Item-Different 75005 12503 (A) Alternating-Pairs NO-SORT NO-SORT (B) Bore-Sight-Simulation Suite Stats: 50000 Items/Target, 0.000000 Seconds 75005 Comparisons, 12503 Exchanges Total Sort Time: 0 Hrs, 0 Mins, 0.5 Secs Generating Targets in [100000 (100000) 100000] Sort Function is FatQsort(Median Pvt) PlotTimer Option is FALSE Items Comparisons Exchanges Code/Target I.D. 100000 NO-SORT NO-SORT (R) Random-Uniform NO-SORT NO-SORT (S) Already-Sorted NO-SORT NO-SORT (V) Reverse-Sorted NO-SORT NO-SORT (H) Reverse-Sorted-by-Halves NO-SORT NO-SORT (F) First-Item-Out-of-Order NO-SORT NO-SORT (T) Every-Third-Item-Inverted NO-SORT NO-SORT (Q) All-Items-Equal NO-SORT NO-SORT (E) Every-Eighth-Item-Different 150005 25003 (A) Alternating-Pairs NO-SORT NO-SORT (B) Bore-Sight-Simulation Suite Stats: 100000 Items/Target, 0.109890 Seconds 150005 Comparisons, 25003 Exchanges Total Sort Time: 0 Hrs, 0 Mins, 0.16 Secs Generating Targets in [100000 (100000) 100000] Sort Function is Standard Library Qsort PlotTimer Option is FALSE Items Comparisons Exchanges Code/Target I.D. 100000 NO-SORT NO-SORT (R) Random-Uniform NO-SORT NO-SORT (S) Already-Sorted NO-SORT NO-SORT (V) Reverse-Sorted NO-SORT NO-SORT (H) Reverse-Sorted-by-Halves NO-SORT NO-SORT (F) First-Item-Out-of-Order NO-SORT NO-SORT (T) Every-Third-Item-Inverted NO-SORT NO-SORT (Q) All-Items-Equal NO-SORT NO-SORT (E) Every-Eighth-Item-Different 2500329228 50717 (A) Alternating-Pairs NO-SORT NO-SORT (B) Bore-Sight-Simulation Suite Stats: 100000 Items/Target, 843.626374 Seconds 2500329228 Comparisons, 50717 Exchanges Total Sort Time: 0 Hrs, 14 Mins, 3.68 Secs