From:	Kbwms <Kbwms AT aol DOT com>
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()

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

- Raw text -