Page 91 - DCAP507_SYSTEM_SOFTWARE

Unit 6: Table Processing: Sorting

In the figure 6.2, every column signifies one pass over the numbers interchanging any two Notes
contiguous numbers that are out of order. This specific table is totally sorted in only seven
passes over the data.
In the most awful case, N-I (here, 11) passes would be essential. The Interchange sort is therefore
proficient to exploit whatsoever natural order there may be in the table. Furthermore, on each
pass via the data at least one item is added to the base of the list in perfect order (here the 31 first,
then, 27, then 26, etc.).

Thus, the sort could be made more competent by:
1. Cutting the portion of the sorted list on each pass; and
2. Verifying for early completion.

!

Caution Such an optimized sort should need approximately N*(N–l)/2 comparisons and
2
so should take a time nearly proportional to N .
We would like an even improved sorting method which needs less time. Sorting methods
consists of basic types:
1. Distributive sorts which sort by probing entries one digit at a time;
2. Comparative sorts which sort by contrasting keywords two at a time; and

3. Address calculation sorts that convert a key into an address close to where the symbol is
predictable to end up.

Self Assessment

Fill in the blanks:
4. ………………… sort considers contiguous pairs of items in the table and places them in
order (interchanges them) as necessary.
5. ………………… sorts are sorted by probing entries one digit at a time.
6. ………………… sorts sorted by contrasting keywords two at a time.

7. ………………… sorts are sorted by converting a key into an address close to where the
symbol is predictable to end up.

6.3 Shell Sort

A rapid comparative sort algorithm is because of D.L. Shell and is known as a Shell sort. It 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. However, it starts by contrasting items a
distance “d” apart. This signifies that items that are out of place will be moved more speedily
than a simple interchange sort. In each pass the value of d is decreased generally;

d + 1
d = i
i+1
2
Every item is contrasted with the one located d positions further in the vector of items. If the
higher item consists of a lower value, an exchange is’ performed. The sort prolongs by comparing
the next item in the vector with an item d locations away (if one exists). If an exchange is again
specified, it is performed and the comparison is attempted again with the next entry. This continues

LOVELY PROFESSIONAL UNIVERSITY 85