Mail Archives: djgpp/1998/04/28/12:10:36
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
- Raw text -