摘要：We investigate the following sorting problem: We are given n bins with two balls in each bin. Balls in the ith bin are numbered n+1-i. 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 problem the best known solution requires almost 4/5n2 swaps. In this paper, we show an algorithm which solves this problem using less than 2n2/3 swaps. Since it is known that the lower bound of the number of swaps is ⌈(2n 2)/3⌉=⌈2n2/3-n/3⌉, our result is almost tight. Furthermore, we show that for n=2m+1(m ≥ 0) the algorithm is optimal.
Loading...
