Efficient Algorithms for Sorting <I>k</I>-Sets in Bins

Atsuki NAGAO; Kazuhisa SETO; Junichi TERUYAMA

doi:10.1587/transinf.2015EDP7038

Efficient Algorithms for Sorting k-Sets in Bins

Atsuki NAGAO, Kazuhisa SETO, Junichi TERUYAMA

Full Text Views

0

Share
Cite this

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.

Publication: IEICE TRANSACTIONS on Information Vol.E98-D No.10 pp.1736-1743

Publication Date: 2015/10/01

Publicized

Online ISSN: 1745-1361

DOI: 10.1587/transinf.2015EDP7038

Type of Manuscript: PAPER

Category: Fundamentals of Information Systems

Authors

Atsuki NAGAO
  Kyoto University,Research Fellow of Japan Society for the Promotion of Science
Kazuhisa SETO
  Seikei University
Junichi TERUYAMA
  National Institute of Informatics,JST, ERATO, Kawarabayashi Large Graph Project

Keyword

greedy, mathematical puzzles, recursion, sorting, swap

Cite this

Copy

Atsuki NAGAO, Kazuhisa SETO, Junichi TERUYAMA, "Efficient Algorithms for Sorting k-Sets in Bins" in IEICE TRANSACTIONS on Information, vol. E98-D, no. 10, pp. 1736-1743, October 2015, doi: 10.1587/transinf.2015EDP7038.
Abstract: 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.
URL: https://globals.ieice.org/en_transactions/information/10.1587/transinf.2015EDP7038/_p

Copy

@ARTICLE{e98-d_10_1736,
author={Atsuki NAGAO, Kazuhisa SETO, Junichi TERUYAMA, },
journal={IEICE TRANSACTIONS on Information},
title={Efficient Algorithms for Sorting k-Sets in Bins},
year={2015},
volume={E98-D},
number={10},
pages={1736-1743},
abstract={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.},
keywords={},
doi={10.1587/transinf.2015EDP7038},
ISSN={1745-1361},
month={October},}

Copy

TY - JOUR
TI - Efficient Algorithms for Sorting k-Sets in Bins
T2 - IEICE TRANSACTIONS on Information
SP - 1736
EP - 1743
AU - Atsuki NAGAO
AU - Kazuhisa SETO
AU - Junichi TERUYAMA
PY - 2015
DO - 10.1587/transinf.2015EDP7038
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E98-D
IS - 10
JA - IEICE TRANSACTIONS on Information
Y1 - October 2015
AB - 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.
ER -