Civil Engineering Reference
In-Depth Information
// Copy array Y back to array X
Loop i = 1,n
X
i
= Y
i
End loop i }
2.6.5 Comparison of the sorting methods
The sorting methods are to be tested with three sets of data of different characteristics. The
first set consists of evenly distributed data, which are generated by the function
x
i
= sin (i + 0.23)
i = 1, n
The results are shown in Table 2.1 where
count
is the total number of data in all the lists
sorted by quick sort or the total number of data in all the bins sorted by bin sort. Hence,
count
is a direct measure of complexity with respect to the number of data points n.
Time
is the CPU
time of Intel
®
Core™ i7 CPU 870@2.93GHz running Visual Fortran in XP mode. The
count
and the CPU time taken by the four sorting methods for n = 10
2
, 10
3
, …, 10
7
are plotted in
Figure 2.38. As shown in Table 2.1, bubble sort and insertion sort are obviously
O
(n
2
) algo-
rithms, as the CPU time increases by 100 times for each step of increment of n by 10 times. A
direct comparison between the bubble sort and insertion sort reveals that the insertion sort is
about twice more efficient than the bubble sort. As the
O
(n
2
) trend complexity is clear, the tests
Table 2.1
Counts and CPU time for sorting of data set 1
Quick sort
Quick sort*
Bin sort
Bubble
Insert
n
Count
Time(s)
Count
Time(s)
Count
Time(s)
Time(s)
Time(s)
100
681
9.77E-6
681
1.04E-5
148
1.31E-5
4.04E-5
1.9E-5
1000
11,799
1.42E-4
11,799
1.45E-4
2096
1.90E-4
3.6E-3
1.74E-3
10,000
165,812
0.00186
165,812
0.00197
21,767
0.00203
0.378
0.173
100,000
2,110,329
0.0196
2,110,329
0.0241
141,907
0.0133
37.6
17.5
1,000,000
25,852,531
0.284
25,852,531
0.292
1,622,397
0.21
10,000,000
316,774,234
3.34
316,774,234
3.48
14,974,655
3.29
1E + 09
100,000,000
10,000,000
Quick_C
1,000,000
100,000
Quick*_C
Bin_C
10,000
1000
100
Quick_T
Quick*_T
10
1
0.1
Bin_T
0.01
0.001
Bobble
Insert
0.0001
0.00001
1
10
100
1000
10,000
100,000 1,000,000 10,000,000
Number of data
Figure 2.38
Data set 1: x(i) = sin(i + 0.23).
