K-sorted sequence

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

In computer science, a nearly-sorted sequence, also known as roughly-sorted sequence and as 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 -sorting is the operation of reordering the elements of a sequence so that it becomes k -sorted. k -sorting is generally more efficient than sorting. Similarly, sorting a sequence is easier if it is known that the sequence is k -sorted. So if a program needs only to consider k -sorted sequences as input or output, considering 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. Given a 2k -sorted sequence \alpha=[a_1,\dots, a_n] , it is possible to compute a (k-1) -sorted permutation \alpha' of \alpha in linear time and constant space. First, given a sequence \beta=[b_1,\dots,b_{2k}] , lets say that this sequence is partitioned if the k -smaller elements are in [b_1,\dots,b_k] and the k -greater elements are in [b_{k+1},\dots, b_{2k}] . Lets call partitioning the action of reordering the sequence \beta into a partitioned permutation. This can be done in linear time by first finding the median of b and then moving elements to the first or second half depending on whether they are smaller or greater than the median. The sequence \alpha' can be obtained by partitioning the blocks of elements at position [2k(i-1)+1, \dots, 2ki] , then by partitioning the blocks of elements at position [2k(i-1)+k+1, \dots, 2ki+k] , and then again the elements at position [2k(i-1)+1, \dots, 2ki] for each number i such that those sequences are defined. Using \frac{n}{2k} processors, with no shared read nor write access to memory, the same algorithm can be applied in O(k) time, since each partition of a sequence can occur in parallel. Merging two k -sorted sequences \alpha^1=[a^1_1,\dots, a^1_n] and \alpha=[a^2_1,\dots, a^2_m] can be done in linear time and constant space. First, using the preceding algorithm, both sequences should be transformed into k/2 -sorted sequences. Let's construct iteratively an output sequence \omega by removing content from both \alpha^i and adding it in \omega . If both \alpha^i 's are empty, then it suffices to return \omega . Otherwise, let us assume that \alpha^1 is empty and not \alpha^2 , it suffices to remove the content of \alpha^2 and append it to \omega . The case where \alpha^2 is empty and not \alpha^1 is similar by symmetry. Let us consider the case where neither \alpha^i is empty. Let us call A^1=\max(a^1_i\mid 1\le i\le k/2) and A^2=\max(a^2_i\mid 1\le i\le k/2) , they are the greatest of the k/2 -firsts elements of each list. Let us assume that A^1 , the other case is similar by symmetry. Remove a^1_1,\dots, a^1_{k/2} from \alpha^1 and remove \{a^2_j\mid 1\le j\le k/2, a^2_j\le A^1\} from \alpha^2 and add them to \omega . Since each sequence \alpha=[a_1,\dots, a_n] is necessarily n -sorted, it suffices to apply the halving algorithm \log_{2}\left(\frac{n}{k}\right) -times. Thus, k -sorting can be done in O(n\log (n/k)) -time. This algorithm is Par-optimal, that is, there exists no sequential algorithm with a better worst-case complexity.

Applications

Nearly-sorted sequences are particularly useful when the exact order of element has little importance. For example, Twitter nearly sorts 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.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1361527021 under CC BY-SA 4.0; modifications have been made.