Section 8.2 Sorting Terminology
The Sorting Problem, as defined, allows input with multiple records having the same key value. However, certain applications require input without duplicate key values. In most cases, sorting algorithms can handle duplicate key values unless explicitly specified otherwise. When duplicates are allowed, there might be an implicit ordering among them based on their occurrence in the input. Preserving this initial ordering among duplicates can be desirable. A sorting algorithm is considered stable if it maintains the relative ordering of records with identical key values. Many of the sorting algorithms discussed in this chapter are stable or can be modified to achieve stability with minor adjustments.
When comparing sorting algorithms, a straightforward approach is to implement both algorithms and measure their running times. This empirical comparison method, however, can be challenging to execute fairly, as the running time of sorting algorithms often depends on specific characteristics of the input values. Factors such as the number of records, key and record sizes, range of key values, and the degree of disorder in the input can significantly impact the relative running times of sorting algorithms.
Traditionally, the analysis of sorting algorithms focuses on measuring the cost in terms of the number of comparisons made between keys. This measure is closely related to the actual running time and offers the advantage of being independent of the specific machine or data type used. However, in certain cases, if the records are large, the physical movement of records during sorting can contribute significantly to the overall running time. In such situations, it may be appropriate to measure the cost by counting the number of swap operations performed by the algorithm. In most applications, it is assumed that all records and keys have a fixed length, and that comparisons and swaps have a constant time complexity regardless of the keys involved. However, special situations arise where the rules for comparing sorting algorithms change. For example, when dealing with records or keys of varying lengths (e.g., sorting variable-length strings), not all comparisons can be assumed to have roughly the same cost. These scenarios require specific analysis techniques and often benefit from specialized sorting techniques tailored to the specific requirements.
You have attempted of activities on this page.
