Correcting Sorted Sequences in a Single Hop Radio Network
Marcin Kik
Abstract
By k-disturbed sequence we mean a sequence obtained from a sorted
sequence by changing the values of at most k elements. We present an
algorithm for single-hop radio networks that sorts a k-disturbed
sequence of length n (where each station stores single key) in time
4n+k(ceil{log k}^2+ceil{log(n-k+1)}+6 ceil{log k})-2 with energetic cost
3 ceil{ (ceil{log k}+1)(ceil{log k}+2)} / (2 floor{n/k} } +
4 ceil{ ceil{log k} / floor{n/k} } + 10. If
(ceil{log k}+1)(ceil{log k}+2)/2 + ceil{log k} <= floor{n/k}
then the energetic cost is bounded by 14.