Fundamentals - Finite Element Mesh Generation - page 52

The weakness of quick sort on equal valued data can be easily rectified. The main dif-
ficulty is due to the improper placement of the pivot always at the first position for a list of
equal valued data instead of at the middle. What has to be done is to replace the statement
in Procedure Pivot (A, I, J, IP) , ' If (T < P) then ' by ' If (T < P or T = P and IP < K) then '. In
case of equal valued data, T = P , IP would not stop at the first position but would proceed
to the K th position right at the middle of the list. This modification has been implemented
and tested, and the enhanced algorithm is denoted by quick sort*. As shown in Table 2.2,
the quick sort* takes slightly more CPU time as compared to the quick sort to sort an array
of small size, say, n = 100. For larger n = 10 3 onwards, the quick sort* takes much less CPU
time than the quick sort, and as indicated by the count , the nlog(n) complexity trend is
recovered for large n's. For evenly distributed data as shown in Table 2.1, the quick sort*
only takes a few percent more CPU time compared to the quick sort.
The third set of data consists of widely spread and equal values of ±10 43 , which are gener-
ated by the function

x i = exp (mod(i,100) + 0.1) sin (mod(i,17) + 0.23) i = 1, n

Again, only the quick sort, quick sort* and bin sort are tested, and the results are shown
in Table 2.3. The count and the CPU times taken are plotted in Figure 2.40. As shown in
Table 2.3, the bin sort takes slightly more CPU time as compared to the sorting of the set of

Table 2.3 Counts and CPU time for sorting of data set 3

Quick sort Quick sort* Bin sort

n Count Time(s) Count Time(s) Count Time(s)

100 763 1.02E-5 763 1.05E-5 998 9.20E-5

1000 12,413 1.43E-4 12,413 1.47E-4 8766 8.00E-4

10,000 183,760 1.93E-3 172,779 2.10E-3 76,384 6.12E-3

100,000 4,454,447 0.0283 1,891,357 0.0216 630,294 0.049

1,000,000 308,302,121 1.14 23,348,533 0.247 5,474,122 0.416

10,000,000 29,563,195,747 95.0 272,169,661 2.75 48,964,710 3.78

1E + 11

1E + 10

1E + 09

Quick_C

100,000,000

10,000,000

Quick*_C

1,000,000

100,000

Bin_C

10,000

1000

Quick_T

100

10

Quick*_T

1

0.1

Bin_T

0.01

0.001

0.0001

0.00001

1 10 100 1000 10,000 100,000 1,000,00010,000,000

Number of data

Figure 2.40 Data set 3: x(i) = exp(mod(i,100) + 0.1)sin.