From: Kbwms <Kbwms AT aol DOT com>
Message-ID: <3d7646f9.3545ff42@aol.com>
Date: Tue, 28 Apr 1998 12:09:36 EDT
To: djgpp AT delorie DOT com
Mime-Version: 1.0
Subject: Library Function qsort() Exhibits N^2 Behavior
Content-type: text/plain; charset=US-ASCII
Content-transfer-encoding: 7bit
Precedence: bulk

The standard library utility qsort() exhibits the dreaded quadratic
behavior on some sort targets.  Some years ago, I wrote a program
that tests sort functions.  The program was described in an article
that was published in an issue of C/C++ Users Journal.  Here is what
my test says when qsort() is run on various kinds of targets, each
20,000 in size:

Generating Targets in [20000 (20000) 20000]
Sort Function is Standard Library Qsort

  Items  Comparisons  Exchanges  Code/Target I.D.
  20000       334037      90599  (R) Random-Uniform
              270865          0  (S) Already-Sorted
              270866      10000  (V) Reverse-Sorted
              900881      93906  (H) Reverse-Sorted-by-Halves
              477073      24711  (F) First-Item-Out-of-Order
              272199      16413  (T) Every-Third-Item-Inverted
              270865          0  (Q) All-Items-Equal
              281338      11973  (E) Every-Eighth-Item-Different
           100050088      10198  (A) Alternating-Pairs
            51016508      19671  (B) Bore-Sight-Simulation
Suite Stats: 20000 Items/Target, 146.978022 Seconds
	     154144720 Comparisons, 277471 Exchanges

Total Sort Time: 0 Hrs, 2 Mins, 27.3 Secs

The Alternating-Pairs target is an array of numbers 1,0,1,0,...
The behavior of qsort() on this target is .25*N^2.

The Bore-Sight-Simulation target consists of data centered about
180, plus or minus 3.  The first dozen elements look like this:

    1    179
    2    180
    3    180
    4    180
    5    180
    6    180
    7    180
    8    181
    9    180
   10    180
   11    181
   12    180

The behavior of qsort() on this target is .125*N^2.


Here are the results from another version of qsort():

Generating Targets in [20000 (20000) 20000]
Sort Function is FatQsort(Median Pvt)

  Items  Comparisons  Exchanges  Code/Target I.D.
  20000       304463      82411  (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, 3.076923 Seconds
	     1730839 Comparisons, 272086 Exchanges

Total Sort Time: 0 Hrs, 0 Mins, 3.13 Secs