Sort well with energy-constrained comparisons
METADATA ONLY
Loading...
Author / Producer
Date
2016-10-28
Publication Type
Working Paper
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
Abstract
We study very simple sorting algorithms based on a probabilistic comparator model. In our model, errors in comparing two elements are due to (1) the energy or effort put in the comparison and (2) the difference between the compared elements. Such algorithms keep comparing pairs of randomly chosen elements, and they correspond to Markovian processes. The study of these Markov chains reveals an interesting phenomenon. Namely, in several cases, the algorithm which repeatedly compares only adjacent elements is better than the one making arbitrary comparisons: on the long-run, the former algorithm produces sequences that are "better sorted". The analysis of the underlying Markov chain poses new interesting questions as the latter algorithm yields a non-reversible chain and therefore its stationary distribution seems difficult to calculate explicitly.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
Pages / Article No.
1610.09223
Publisher
Cornell University
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Organisational unit
03340 - Widmayer, Peter (emeritus) / Widmayer, Peter (emeritus)
Notes
Funding
165524 - Energy-Tunable Combinatorial Algorithms (SNF)
Related publications and datasets
Is previous version of: