This page briefly introduces the use of sorting.
Understanding data characteristics
Using sorting to process data helps us understand its characteristics and facilitates subsequent analysis and visualization. In everyday examples such as dictionaries and menus, if items are not arranged in a certain order, the time people need to find what they want increases greatly.
Computers need to process large-scale data. After sorting, people can design the subsequent processing flow according to the characteristics and requirements of the data.
Reducing time complexity
Using sorting as preprocessing can reduce the time complexity required to solve a problem; it is usually a trade-off of space for time. If a sorted list needs to be analyzed multiple times, spending the resources required for sorting only once is worthwhile, because each subsequent analysis can reduce a great deal of time.
Example: Checking whether a given sequence contains equal elements
Consider a sequence. You need to check whether any of its elements are equal.
A naive approach is to check every pair of numbers and determine whether the pair is equal. The time complexity is .
We may as well sort this sequence first. It is then easy to see that if two numbers are equal, they must be adjacent in the new sequence. At that point, we only need to scan the new sequence once in time.
The overall time complexity is the sorting complexity, .
Preprocessing for searching
Sorting is the preprocessing required by binary search. After sorting, binary search can find a specified element in a sequence in time.