Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
On partitions and presortedness of sequences
Luleå tekniska universitet.
Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering, Computer Science.
1992 (English)In: Acta Informatica, ISSN 0001-5903, E-ISSN 1432-0525, Vol. 29, no 3, p. 267-280Article in journal (Refereed) Published
Abstract [en]

To take advantage of existing order in a sequence when sorting, we evaluate the quantity of this information by the minimal size of decomposition of the input sequence, particularly the minimal size of chain and of monotonic partitions. Some sorting strategies that are optimal with respect to these measures of presortedness are presented. The relationships between these new measures of presortedness and other known measures have also been explored. As an application, we carry out the optimality of an adaptive sorting algorithm Skiena'sMelsort. For some special partitioning strategies, we present two sorting algorithms based on Dijkstra'sSmoothsort. Moreover, the optimalities of these two algorithms are demonstrated. By examining the optimalities of sorting algorithms with respect to certain measures of presortedness, we also propose some optimal sorting strategies for one class of measures. Finally, we discuss other types of sorting problems, such as sorting multisets and topological sorting. In particular, we derive an optimal algorithm for sorting multisets and for finding the multiset sizes as well.

Place, publisher, year, edition, pages
1992. Vol. 29, no 3, p. 267-280
National Category
Computer Sciences
Research subject
Dependable Communication and Computation Systems
Identifiers
URN: urn:nbn:se:ltu:diva-5170DOI: 10.1007/BF01185681ISI: A1992HX46000003Scopus ID: 2-s2.0-0026883118Local ID: 333e0310-b6a6-11db-abff-000ea68e967bOAI: oai:DiVA.org:ltu-5170DiVA, id: diva2:978044
Note
Godkänd; 1992; 20070207 (evan)Available from: 2016-09-29 Created: 2016-09-29 Last updated: 2018-07-10Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records BETA

Chen, Jingsen

Search in DiVA

By author/editor
Chen, Jingsen
By organisation
Computer Science
In the same journal
Acta Informatica
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 44 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf