Lesson plan
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.
Article summary
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.
Key claims
No claims recorded.
Discussion questions
- Summarise the article in your own words. Which single claim would you verify first, and why?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- If two sources disagreed about one of these facts, what would you need in order to trust one over the other?
Bibliography
No sources recorded.
Key claims and bibliography are generated from the same tracked claims and sources as the article page.