Page 89 - DCAP507_SYSTEM_SOFTWARE

Unit 6: Table Processing: Sorting

6.1.1 Classification of Sorting Notes

Sorting can be classified in two types:
(i) Internal Sorting
(ii) External Sorting

Internal Sorting: If the records that have to be sorted are in the internal memory.
External Sorting: If the records that have to be sorted are in secondary memory.

Efficiency Considerations

The most important considerations are:
1. The amount of machine time necessary for running the program.
2. The amount of space necessary for the program.
In most of the computer applications one is optimized at the expense of another. The actual time
units to sort a file of size n varies from machine to machine, from one program to another, and
from one set of data to another.
So, we find out the corresponding change in the amount of time required to sort a file induced
by a change in the file size n.

Note The time efficiency is not measured by the number of time units required but
rather by the number of critical operations performed.
Critical operations are those that take most of the execution time.

Example: Key comparisons (that is, the comparisons of the key of two records in the file
to determine which is greater), movement of records or pointer to record, or interchange of two
records.

Task Make distinction between internal sorting and external sorting.

Self Assessment

Fill in the blanks:
1. If the records that have to be sorted are in the internal memory, it is called …………………
sorting.
2. If the records that have to be sorted are in secondary memory, it is called …………………
sorting.

3. ………………… refers to the operation of arranging data in some given order, such as
increasing or decreasing, with numerical data or alphabetically, with character data.

LOVELY PROFESSIONAL UNIVERSITY 83