On-line sorting of twisted sequences in linear time (Q1104753)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: On-line sorting of twisted sequences in linear time |
scientific article; zbMATH DE number 4057016
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | On-line sorting of twisted sequences in linear time |
scientific article; zbMATH DE number 4057016 |
Statements
On-line sorting of twisted sequences in linear time (English)
0 references
1988
0 references
A sequence of real numbers is called twisted if it can be produced from the sorted sequence by repeatedly reversing the order of consecutive subsequences. It is shown that twisted sequences constitute a class of exponentially many members each of which can be recognized and sorted, by a simple on-line algorithm, in linear time.
0 references
sorting
0 references
worst-case complexity
0 references
twisted sequences
0 references
0 references
0 references
0.8409494
0 references
0.8401673
0 references
0.83921474
0 references
0.8350445
0 references
0.83349216
0 references
0.8277127
0 references
0.8272079
0 references
