Page 93 - DCAP507_SYSTEM_SOFTWARE

Unit 6: Table Processing: Sorting

Notes
Example: Consider the radix sorting of the numbers as displayed in Figure 6.4. You
should be able to discover rather quickly the functioning of this sort. Actually, this is exactly the
method utilized on a card sorting machine.

Figure 6.4: Demonstration of Radix Sorting

Original First Second Final
table distribution Merge distribution merge
19 01 01
13 0) 31 0) 01,02,05,09 02
05 1) 01,31,11,21 11 1) 11,13,16,19 05
27 2) 02 21 2) 21,26,27 09
01 3) 13 02 3) 31 11
26 4) 13 4) 13
31 5) 05 05 5) 16
16 6) 26,16 26 6) 19
02 7) 27 16 7) 21
09 8) 27 8) 26
11 9) 19,09 19 9) 27
21 09 31
 
Separate, based Separate, based
on last digit on first digit

However, there are some drawbacks to using it internally on a digital computer

1. It takes two different processes, a separation and a merge; and
2. It needs a lot of extra storage for the buckets. However, this last drawback can be conquered
by chaining records inside a logical “bucket” instead of pre-allocating maximum size
buckets.

Self Assessment

Fill in the blanks:
11. Bucket sort is also known as ………………… sort.

12. A number system of base P needs P ………………… .

6.5 Radix Exchange Sort

A significantly better distributive sort is the radix exchange sort which is valid when the keys
are expressed, (or are expressible) in binary. Sorting is achieved by considering groups with the
similar (M) first bits and ordering that group regarding the (M+ l)st bit. The ordering of a group
on a specified bit is achieved by scanning down from the top of the group for a one bit and up
from the bottom for a zero bit; these two are exchanged and the sort goes on.
This algorithm needs the program to continue with a huge number of groups and, coded in a bad
form, could need an additional table N long. However, with optimal coding it is probable to
follow the groups by just observing the top of the table and a list of break points, one for each bit
of the key- word. (Therefore with 32 bit words a table of only 33 entries is needed.)

LOVELY PROFESSIONAL UNIVERSITY 87