Page 94 - DCAP507_SYSTEM_SOFTWARE

System Software

Notes If the sort algorithm is programmed to quit sorting when a group includes only one item, then
the time needed for the radix exchange sort is proportional to N*log(N) as compared to N*log (K)
p
for the bucket sort (here K is the maximum key size and p is the radix).

Note The radix exchange sort does not need additional table space for “buckets.”

Task Make distinction between radix sort and radix exchange sort.

Self Assessment

Fill in the blanks:

13. A ………………… sort is valid when the keys are expressed, (or are expressible) in binary.
14. Sorting is achieved by considering groups with the similar (M) first bits and ordering that
group regarding the ………………… bit.

15. If the sort algorithm is programmed to quit sorting when a group includes only one item,
then the time needed for the radix exchange sort is proportional to N*log(N) as compared
to ………………… for the bucket sort.

6.6 Summary

 Efficient and reliable data processing depends upon sorted data.
 The internal and external sorting methods have their relative efficiencies in different
applications.
 Interchange sort is a simple sort that considers contiguous pairs of items in the table and
places them in order (interchanges them) as necessary.
 Shell sort leads to best possible performance for a comparative type of sort.
 The Shell sort is analogous to the interchange sort as it shifts data items by exchanges.
 Bucket 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.
 A significantly better distributive sort is the radix exchange sort which is valid when the
keys are expressed, (or are expressible) in binary.
 The radix exchange sort does not need additional table space for “buckets.”

6.7 Keywords

Bucket Sort: Bucket 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.
Interchange Sort: Interchange sort is a simple sort that considers contiguous pairs of items in the
table and places them in order (interchanges them) as necessary.

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.

88 LOVELY PROFESSIONAL UNIVERSITY