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
Linear-time in-place selection in less than 3n comparisons
Luleå tekniska universitet.
1995 (English)In: Proceedings of the 6th International Symposium on Algorithms and Computation: ISAAC'95 / [ed] John Staples, Berlin: Encyclopedia of Global Archaeology/Springer Verlag, 1995, 244-253 p.Conference paper, Published paper (Refereed)
Abstract [en]

By developing and exploiting new in-place techniques, we show that finding the element with the median value out of n elements stored in an array can be performed in-place in (2.95 + e)n (for any c > 0) comparisons and in linear time. This is arbitrarily close to the upper bound for the same problem without space-restrictions. To make the algorithm competitive we also try to minimize the number of element moves performed by the algorithm since this is the other critical operation. This has resulted in a trade-off between the number of comparisons and the number of moves. By minimizing the sum of the critical operations we achieve an algorithm that uses at most 3.75n comparisons and 9n moves for finding the median in-place. This is, in principle, twice as good as earlier attempts on implicit selection for both of the operations.

Place, publisher, year, edition, pages
Berlin: Encyclopedia of Global Archaeology/Springer Verlag, 1995. 244-253 p.
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 1004
National Category
Computer Sciences
Research subject
Dependable Communication and Computation Systems
Identifiers
URN: urn:nbn:se:ltu:diva-34687DOI: 10.1007/BFb0015429Local ID: 8f465c70-a287-11dc-ac39-000ea68e967bISBN: 3-540-60573-8 (print)OAI: oai:DiVA.org:ltu-34687DiVA: diva2:1007938
Conference
International Symposium on Algorithms and Computation : 04/12/1995 - 06/12/1995
Note
Godkänd; 1995; 20071204 (ysko)Available from: 2016-09-30 Created: 2016-09-30Bibliographically approved

Open Access in DiVA

fulltext(628 kB)10 downloads
File information
File name FULLTEXT01.pdfFile size 628 kBChecksum SHA-512
abce59f881f36abf0815ee0e57b7541169bde79252e0991592c664ef0e8646f8a2b2ff08bcb0e938a579b1e284808276c699ff720fa51f66aa58b7fe8e0f2810
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

By author/editor
Sundström, Mikael
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 10 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 12 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