From: Kbwms 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 Content-type: text/plain; charset=US-ASCII Content-transfer-encoding: 7bit Precedence: bulk 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