From: Kbwms AT aol DOT com Message-ID: <93d8c6c.36058c82@aol.com> Date: Sun, 20 Sep 1998 19:15:14 EDT To: dj AT delorie DOT com Cc: djgpp-workers AT delorie DOT com Mime-Version: 1.0 Subject: Re: Much Improved Version of qsort Content-type: text/plain; charset=US-ASCII Content-transfer-encoding: 7bit Precedence: bulk Dear DJ Delorie, I have finished work on a new version of qsort that is substantially better that the current version in our library. To show that this is so, I append to this letter the results of two test runs. The first shows the results of the current qsort, the second on the new version. Each test run consists of two passes on the test program. Each pass calls qsort 10 times to sort a different kind of sort target on each call. On the first pass, each sort target consists of 20,000 items. On the second pass, each sort target consists of 40,000 items. As can be seen in the timing figures in the result printouts below, our current version of qsort demonstrates quadratic timing behavior on two of the sort targets. These sort targets are the last two in the list. As you can see, the numbers of comparisons are virtually quadrupled on targets that are double the size. Similar runs are shown for the new version of qsort. As you can see, the numbers of comparisons are much smaller for the targets at issue. No such quadratic timing behavior is demonstrated. On my Pentium 1: Total sort time for the current version of qsort: 287.74 secs. Total sort time for the new version of qsort: 3.35 secs. Posted on ftp.delorie.com/incoming is tstqsort.zip that contains the following files: 1. fqsort.c - the proposed new fat-pivot version of qsort. 2. lqsort.c - the current library version of qsort. This version has hooks inserted to count swaps. 3. tstsort.c - a test driver for any sort function that has a qsort-like calling protocol. 4. a header file, tsrtdefs.h, and five C-source files, with extension .cin, that are included by tstsort.c. 5. a makefile 6. two result files identical to the stuff that is appended to this letter - fqsort.out and lqsort.out. 7. a readme file that explains how the program works. The makefile prepares two executables - fqsort.exe and lqsort.exe. To duplicate the printouts appended below, execute each with the following command lines: lqsort N 20000 20000 40000 > lqsort.x fqsort N 20000 20000 40000 > fqsort.x Then, compare the new .x files with the corresponding .out files from the zip archive. Except for the timing figures, the files should compare exactly. Remember, lqsort (the library version) will take substantially longer than fqsort to run. K.B. Williams ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Generating Targets in [20000 (20000) 40000] Sort Function is Standard Library Qsort PlotTimer Option is FALSE Items Comparisons Exchanges Code/Target I.D. 20000 315228 77650 (R) Random-Uniform 270865 0 (S) Already-Sorted 270866 10000 (V) Reverse-Sorted 900881 83589 (H) Reverse-Sorted-by-Halves 477073 19998 (F) First-Item-Out-of-Order 272199 6666 (T) Every-Third-Item-Inverted 270865 0 (Q) All-Items-Equal 281338 10629 (E) Every-Eighth-Item-Different 100050088 10195 (A) Alternating-Pairs 51016508 19662 (B) Bore-Sight-Simulation Suite Stats: 20000 Items/Target, 58.131868 Seconds 154125911 Comparisons, 238389 Exchanges Items Comparisons Exchanges Code/Target I.D. 40000 689461 169508 (R) Random-Uniform 581714 0 (S) Already-Sorted 581715 20000 (V) Reverse-Sorted 2043983 177877 (H) Reverse-Sorted-by-Halves 1034071 39998 (F) First-Item-Out-of-Order 584387 13333 (T) Every-Third-Item-Inverted 581714 0 (Q) All-Items-Equal 603311 22460 (E) Every-Eighth-Item-Different 400120590 20398 (A) Alternating-Pairs 198488228 38612 (B) Bore-Sight-Simulation Suite Stats: 40000 Items/Target, 229.505495 Seconds 605309174 Comparisons, 502186 Exchanges Total Sort Time: 0 Hrs, 4 Mins, 47.74 Secs ======================================================================== Generating Targets in [20000 (20000) 40000] Sort Function is Fat-Pivot Quicksort (Median Pivots) PlotTimer Option is FALSE Items Comparisons Exchanges Code/Target I.D. 20000 313077 81837 (R) Random-Uniform 240010 4094 (S) Already-Sorted 260621 29998 (V) Reverse-Sorted 271539 83970 (H) Reverse-Sorted-by-Halves 260620 19998 (F) First-Item-Out-of-Order 252503 30602 (T) Every-Third-Item-Inverted 20003 1 (Q) All-Items-Equal 64460 9927 (E) Every-Eighth-Item-Different 30005 5003 (A) Alternating-Pairs 26615 6082 (B) Bore-Sight-Simulation Suite Stats: 20000 Items/Target, 1.043956 Seconds 1739453 Comparisons, 271512 Exchanges Items Comparisons Exchanges Code/Target I.D. 40000 661261 173685 (R) Random-Uniform 520011 8190 (S) Already-Sorted 561233 59998 (V) Reverse-Sorted 585485 178978 (H) Reverse-Sorted-by-Halves 561232 39998 (F) First-Item-Out-of-Order 544413 53404 (T) Every-Third-Item-Inverted 40003 1 (Q) All-Items-Equal 134495 21056 (E) Every-Eighth-Item-Different 60005 10003 (A) Alternating-Pairs 53077 11971 (B) Bore-Sight-Simulation Suite Stats: 40000 Items/Target, 2.197802 Seconds 3721215 Comparisons, 557284 Exchanges Total Sort Time: 0 Hrs, 0 Mins, 3.35 Secs