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.
Attributes | Values |
---|
rdf:type
| |
rdfs:label
| |
rdfs:comment
| - 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. (en)
|
differentFrom
| |
dcterms:subject
| |
Wikipage page ID
| |
Wikipage revision ID
| |
Link from a Wikipage to another Wikipage
| |
sameAs
| |
dbp:wikiPageUsesTemplate
| |
has abstract
| - 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 nearly sort the 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 , 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. (en)
|
prov:wasDerivedFrom
| |
page length (characters) of wiki page
| |
foaf:isPrimaryTopicOf
| |
is Link from a Wikipage to another Wikipage
of | |
is Wikipage redirect
of | |
is foaf:primaryTopic
of | |