K-sorted sequence

In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, 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.
The nearly-sorted sequences are particularly useful when the exact order of element has little importance. For example <a href="/facts/Twitter/VWwDNGUm">Twitter</a> 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 <a href="/facts/Snowflake_ID/LANgkS6z">Snowflake IDs</a>.

 
 
 
 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.

K-sorted sequence open-in-new

K-sorted sequence