In computer science, a nearly-sorted sequence, also known as roughly-sorted sequence and as k {\displaystyle k} -sorted sequence is a sequence which is almost ordered. By almost ordered, it is meant that no element of the sequence is very far away from where it would be if the sequence were perfectly ordered. It is still possible that no element of the sequence is at the place where it should be if the sequence were perfectly ordered.
k {\displaystyle k} -sorting is the operation of reordering the elements of a sequence so that it becomes k {\displaystyle k} -sorted. k {\displaystyle k} -sorting is generally more efficient than sorting. Similarly, sorting a sequence is easier if it is known that the sequence is k {\displaystyle k} -sorted. So if a program needs only to consider k {\displaystyle k} -sorted sequences as input or output, considering k {\displaystyle k} -sorted sequences may save time. The radius of a sequence is a measure of presortedness, that is, its value indicate how much the elements in the list has to be moved to get a totally sorted value. In the above example of tweets which are sorted up to the second, the radius is bounded by the number of tweets in a second.
Definition Given a positive number k {\displaystyle k} , a sequence [ a 1 , … , a n ] {\displaystyle [a_{1},\dots ,a_{n}]} is said to be k {\displaystyle k} -sorted if for each 1 ≤ i {\displaystyle 1\leq i} and for each i + k ≤ j ≤ n {\displaystyle i+k\leq j\leq n} , a i ≤ a j {\displaystyle a_{i}\leq a_{j}} . That is, the sequence has to be ordered only for pairs of elements whose distance is at least k {\displaystyle k} . The radius of the sequence α {\displaystyle \alpha } , denoted ROUGH ( α ) {\displaystyle {\text{ROUGH}}(\alpha )} or Par ( α ) {\displaystyle {\text{Par}}(\alpha )} is the smallest k {\displaystyle k} such that the sequence is k {\displaystyle k} -sorted. The radius is a measure of presortedness. A sequence is said to be nearly-sorted or roughly-sorted if its radius is small compared to its length.
Equivalent definition A sequence [ a 1 , … , a n ] {\displaystyle [a_{1},\dots ,a_{n}]} is k {\displaystyle k} -sorted if and only if each range of length 2 k + 2 {\displaystyle 2k+2} , [ a i , a i + 1 , … , a i + 2 k + 2 ] {\displaystyle [a_{i},a_{i+1},\dots ,a_{i+2k+2}]} is k {\displaystyle k} -sorted.
Properties All sequences of length n {\displaystyle n} are ( n − 1 ) {\displaystyle (n-1)} -sorted, that is, 0 ≤ Par ( [ a 1 , … , a n ] ) < n {\displaystyle 0\leq {\text{Par}}([a_{1},\dots ,a_{n}])<n} . A sequence is 0 {\displaystyle 0} -sorted if and only if it is sorted. A k {\displaystyle k} -sorted sequence is automatically ( k + 1 ) {\displaystyle (k+1)} -sorted but not necessarily ( k − 1 ) {\displaystyle (k-1)} -sorted.
Relation with sorted sequences Given a sequence a k {\displaystyle k} -sorted sequence [ a 1 , … , a n ] {\displaystyle [a_{1},\dots ,a_{n}]} and its sorted permutation [ a σ 1 , … , a σ n ] {\displaystyle [a_{\sigma _{1}},\dots ,a_{\sigma _{n}}]} , | i − σ i | {\displaystyle |i-\sigma _{i}|} is at most k {\displaystyle k} .
Algorithms
… excerpt ends here. Continue reading the full article.
