liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • 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 adaptive sorting in sequential and parallel models
Linköping University, Department of Computer and Information Science. Linköping University, The Institute of Technology.
1989 (English)Licentiate thesis, comprehensive summary (Other academic)
Abstract [en]

Sorting is probably the most well-studied problem in computer science. In many applications the elements to be sorted are not randomly distributed, but are already nearly ordered. Most existing algorithms do not take advantage of this fact. In this thesis, the problem of utilizing existing order among the input sequence, yielding adaptive sorting algorithms, is explored. Different measures for measuring existing order are proposed; all motivated by geometric interpretations of the input. Furthermore, several adaptive, sequential and parallel, sorting algorithms are provided.

The thesis consists of three papers. The first paper studies the local insertion sort algorithm of Mannila, and proposes some significant improvements. The second provides an adaptive variant of heapsort, which is space efficient and uses simple data structures. In the third paper, a cost-optimal adaptive parallel sorting algorithm is presented. The model of computation is the EREW PRAM.

Place, publisher, year, edition, pages
Linköping: Univ. , 1989. , p. 44
Series
Linköping Studies in Science and Technology. Thesis, ISSN 0280-7971 ; 166
National Category
Signal Processing
Identifiers
URN: urn:nbn:se:liu:diva-160342Local ID: LiU-Tek-Lic-1989:06ISBN: 91-7870-442-1 (print)OAI: oai:DiVA.org:liu-160342DiVA, id: diva2:1352606
Available from: 2019-09-19 Created: 2019-09-19 Last updated: 2019-09-19Bibliographically approved

Open Access in DiVA

No full text in DiVA

Search in DiVA

By author/editor
Petersson, Ola
By organisation
Department of Computer and Information ScienceThe Institute of Technology
Signal Processing

Search outside of DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 4 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • 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