| doi:10.2201/NiiPi.2012.9.2 |
| An almost optimal algorithm for Winkler's sorting pairs in bins |
| Hiro ITO1, Junichi TERUYAMA2 and Yuichi YOSHIDA3 |
1School of Informatics, Kyoto University, Japan
2School of Informatics, Kyoto University, Japan
3School of Informatics, Kyoto University, and Preferred Infrastructure, Inc., Japan |
(Received: October 30,2011)
(Revised: December 20,2011)
(Accepted: December 22,2011) |
Abstract:
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.
|
Keywords:
Bubble sort, mathematical puzzle, recursion, sorting, swap
|
|
|
| PDF(256KB) | References |
National Institute of Informatics is a member of CrossRef.
|
