Efficient Algorithms for Sorting k-Sets in Bins

Atsuki NAGAO  Kazuhisa SETO  Junichi TERUYAMA  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E98-D   No.10   pp.1736-1743
Publication Date: 2015/10/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2015EDP7038
Type of Manuscript: PAPER
Category: Fundamentals of Information Systems
Keyword: 
greedy,  mathematical puzzles,  recursion,  sorting,  swap,  

Full Text: PDF>>
Buy this Article




Summary: 
We propose efficient algorithms for Sorting k-Sets in Bins. The Sorting k-Sets in Bins problem can be described as follows. We are given numbered n bins with k balls in each bin. Balls in the i-th bin are numbered n-i+1. We can only swap balls between adjacent bins. Our task is to move all of the balls to the same numbered bins. For this problem, we give an efficient greedy algorithm with $ rac{k+1}{4}n^2+O(k+n)$ swaps and provide a detailed analysis for k=3. In addition, we give a more efficient recursive algorithm using $ rac{15}{16}n^2+O(n)$ swaps for k=3.