An almost optimal algorithm for Winkler's sorting pairs in bins (コンピュテーシヨン)

概要

論文の詳細を見る
We investigate the following sorting puzzle: We are given n bins with two balls in each bin. Balls in the ith bin are numbered n-i+1. We can swap two balls from adjacent bins. How many number of swaps are needed in order to sort balls, i.e., move every ball to the bin with the same number. For this puzzle the best known solution requires almost (4n^2)/5 swaps. In this paper, we show an algorithm which solves this puzzle using less than (2n^2)/3 swaps. Since it is known that the lower bound of the number of swaps is [numerical formula],our result is almost tight. Futhermore, we show that for n=2^k+1(k〓0) the algorithm is optimal.
社団法人電子情報通信学会の論文
2010-01-18