From:	Kbwms <Kbwms AT aol DOT com>
Message-ID:	<6c663530.3547817d@aol.com>
Date:	Wed, 29 Apr 1998 15:37:32 EDT
To:	j DOT bischoff AT airbus DOT dasa DOT de
Cc:	djgpp AT delorie DOT com
Mime-Version:	1.0
Subject:	Re: Library Function qsort() Exhibits N^2 Behavior

Dear Jens Bischoff,

On 04-29-98 at 04:23:15 EST you wrote:
>
> Hi!
>
> >
> > The standard library utility qsort() exhibits the dreaded quadratic
> > behavior on some sort targets.
>
>
> No, it doesn't. The qsort algorithm is of order O(n * log(n))
> for the number of EXCHANGES!
> With n = 20000, n * log(n) ~ 285000.
> This value is close to the value that is reported by your program.

Thank you for your response.  The expression O(n*log(n)) represents
a statement of TIMING complexity.  I should have stated that at the
beginning of my previous message.  That GNU qsort() is quadratic in
behavior is shown in runs that are appended to this e-mail.  Here is
a recap:

Items   Comparisons  Exchanges	Timing (Seconds)
-----   -----------  ---------  ----------------
10000	 25024958       5140       8.186813
20000   100050088      10198      32.802198
50000   625125110      25316     208.296703

As you can see, the number of exchanges grows linearly while the
number of comparisons grows quadratically.  Hence, the time will
grow quadratically.  This behavior is exhibited in the timing
results presented in the last column.  The time required to sort
an array that is five times as large is about 25 times as long.


Cordially,
K.B. Williams
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Generating Targets in [10000 (10000) 10000]
Sort Function is Standard Library Qsort

  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
            25024958       5140  (A) Alternating-Pairs
             NO-SORT    NO-SORT  (B) Bore-Sight-Simulation
Suite Stats: 10000 Items/Target, 8.186813 Seconds
	     25024958 Comparisons, 5140 Exchanges

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

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

  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
           100050088      10198  (A) Alternating-Pairs
             NO-SORT    NO-SORT  (B) Bore-Sight-Simulation
Suite Stats: 20000 Items/Target, 32.802198 Seconds
	     100050088 Comparisons, 10198 Exchanges

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

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

  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
           625125110      25316  (A) Alternating-Pairs
             NO-SORT    NO-SORT  (B) Bore-Sight-Simulation
Suite Stats: 50000 Items/Target, 208.296703 Seconds
	     625125110 Comparisons, 25316 Exchanges

Total Sort Time: 0 Hrs, 3 Mins, 28.35 Secs

- Raw text -