delorie.com/archives/browse.cgi   search  
Mail Archives: djgpp-workers/1998/09/20/19:16:04

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

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

- Raw text -


  webmaster     delorie software   privacy  
  Copyright © 2019   by DJ Delorie     Updated Jul 2019