Page 92 - DCAP507_SYSTEM_SOFTWARE

System Software

Notes until no lower items remain, This process is known as bubbling; if you think of low valued items
floating to the top, the behavior in the subprocess is like that of a bubble water lank.

Did u know? After bubbling can no longer take place with a fixed value of d, the process
starts again with a new d.
It is complicated to guess the time requirements of the Shell sort as it is difficult to demonstrate
the effect of one pass on another. It should be clear that if the above method of calculating d is
utilized, the number of passes will be about log (d) as bubbling when d=t will complete the sort.
2
2
Empirical studies have exposed that the Shell sort takes about B*N*(log N) units of time for an
2
N element vector. The constant of proportionality B is quite small, thus for small N the Shell sort
will outperform the radix exchange sort illustrated later in the unit.
Example: We show an example of a shell sort as below in Figure 6.3.

Figure 6.3: Example of a Shell Sort

Pass 1 Pass 2 Pass 3 Pass 4
(d 1 = 6) (d 2 = 3) (d 3 = 2) (d 4 = 1)
19 19 *09 *02 *01
d 4
13 13 *01 d 3 01 *02
d 2
05 *02 02 *09 *05
27 d 1 *09 *19 *05 *09
01 01 **11 11 11
26 *21 *05 **13 13
31 31 *27 **16 16
16 16 **13 *19 19
02 *05 *21 ***21 21
09 *27 *31 *26 26
11 11 *16 *27 27
21 *26 26 *31 31

* = Exchange; ** = Dual exchange; *** = Triple exchange

Self Assessment

Fill in the blanks:

8. ………………… leads to best possible performance for a comparative type of sort.
9. The Shell sort is analogous to the interchange sort as it shifts data items by…………… .
10. Shell sort takes about ………………… units of time for an N element vector.

6.4 Bucket Sort

A simple distributive sort is known as the radix sort or bucket sort. The sort includes probing the
least important digit of the keyword first, and the item is then allocated to a bucket exclusively
dependent on the value of the digit. After distributing all items, the “buckets” items arc combined
in order and then the process is repeated until no more digits are left. A number system of base
P needs P buckets.

86 LOVELY PROFESSIONAL UNIVERSITY