Usage of Sorting

Last translate with upstream: 58b9fe6 on Feb 8, 2021.

This article will briefly introduce the usage of sorting.

Reducing Time Complexity

Using sort, we can reduce the time complexity required to solve the problem.

[Example] Check whether an array have equivalent elements

Consider a sequence of numbers and you need to check whether there are any equal elements.

A straightforward solution is to check each pair of elements and determine whether they are equal. The time complexity is O(n^2) .

We might as well sort this sequence of numbers first, and then it is not difficult to find that if there are two equal numbers, they must be in adjacent positions in the new sequence. At this point, you only need to scan the new sequence for the time complexity of O(n) .

The total time complexity is the sorting time complexity ( O(n\log n) ).

Preprocessing work for searching

Sorting is also the preprocessing work for binary search. By making binary searches after sorting, we can find the specified element in the sequence within the time of O(\log n) .

buildLast update and/or translate time of this article，Check the history
editFound smelly bugs? Translation outdated? Wanna contribute with us? Edit this Page on Github
peopleContributor of this article OI-wiki
translateTranslator of this article Visit the original article!
copyrightThe article is available under CC BY-SA 4.0 & SATA ; additional terms may apply.

Comments