K-sorted sequence

(Redirected from K-sorting)

In computer science, a nearly-sorted sequence, also known as roughly-sorted sequence and as -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.

The nearly-sorted sequences are particularly useful when the exact order of element has little importance. For example Twitter[1] nearly sort tweets, up to the second, as there is no need for more precision. Actually, given the impossibility to exactly synchronize all computers, an exact sorting of all tweets according to the time at which they are posted is impossible. This idea led to the creation of Snowflake IDs.

-sorting is the operation of reordering the elements of a sequence so that it becomes -sorted. -sorting is generally more efficient than sorting. Similarly, sorting a sequence is easier if it is known that the sequence is -sorted. So if a program needs only to consider -sorted sequences as input or output, considering -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

edit

Given a positive number  , a sequence   is said to be  -sorted if for each   and for each  ,  . That is, the sequence has to be ordered only for pairs of elements whose distance is at least  .

The radius of the sequence  , denoted  [2] or  [3] is the smallest   such that the sequence is  -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

edit

A sequence   is  -sorted if and only if each range of length  ,   is  -sorted.

Properties

edit

All sequences of length   are  -sorted, that is,  . A sequence is  -sorted if and only if it is sorted. A  -sorted sequence is automatically  -sorted but not necessarily  -sorted.

Relation with sorted sequences

edit

Given a sequence a  -sorted sequence   and its sorted permutation  ,   is at most  .

Algorithms

edit

Deciding whether a sequence is  -sorted

edit

Deciding whether a sequence   is  -sorted can be done in linear time and constant space by a streaming algorithm. It suffices, for each  , to keep track of   and to check that  .

Computing the radius of a sequence

edit

Computing the radius of a sequence can be computed in linear time and space. This follows from the fact that it can be defined as  .

Halving the radius of a sequence

edit

Given a  -sorted sequence  , it is possible to compute a  -sorted permutation   of   in linear time and constant space.

First, given a sequence  , lets say that this sequence is partitioned if the  -smaller elements are in   and the  -greater elements are in  . Lets call partitioning the action of reordering the sequence   into a partitioned permutation. This can be done in linear time by first finding the median of   and then moving elements to the first or second half depending on whether they are smaller or greater than the median.

The sequence   can be obtained by partitioning the blocks of elements at position  , then by partitioning the blocks of elements at position  , and then again the elements at position   for each number   such that those sequences are defined.

Using   processors, with no shared read nor write access to memory, the same algorithm can be applied in   time, since each partition of a sequence can occur in parallel.

Merging two  -sorted sequences

edit

Merging two  -sorted sequences   and   can be done in linear time and constant space.

First, using the preceding algorithm, both sequences should be transformed into  -sorted sequences.

Let's construct iteratively an output sequence   by removing content from both   and adding it in  .

If both  's are empty, then it suffices to return  . Otherwise, let us assume that   is empty and not  , it suffices to remove the content of   and append it to  . The case where   is empty and not   is similar by symmetry.

Let us consider the case where neither   is empty. Let us call   and  , they are the greatest of the  -firsts elements of each list. Let us assume that  , the other case is similar by symmetry. Remove   from   and remove   from   and add them to  .

Sorting a  -sorted sequence

edit

A  -sorted sequence can be sorted by applying the halving algorithm given above   times. This takes   time on a sequential machine, or   time using   processors.

 -sorting a sequence

edit

Since each sequence   is necessarily  -sorted, it suffices to apply the halving algorithm  -times. Thus,  -sorting can be done in  -time. This algorithm is Par-optimal, that is, there exists no sequential algorithm with a better worst-case complexity.

References

edit
  1. ^ @rk. "Announcing Snowflake". Twitter blog. Retrieved 26 April 2021.
  2. ^ Altman, Tom; Igarashi, Yoshihide (1989-08-25). "Roughly Sorting: Sequential and Parallel Approach". Journal of Information Processing. 12 (2): 154–158.
  3. ^ Estivill-Castro, Vladimir; Wood, Derick (October 1989). "A new measure of presortdness". Information and Computation. 83 (1): 111–119. doi:10.1016/0890-5401(89)90050-3.