| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2016-10-21 13:30 2種類のアイテムに限定した物理的バケットソート ○長尾篤樹・吉澤修平・伊藤大雄（電通大）  COMP2016-26 |
|
| 抄録 | （和） | ソートの対象となるアイテムの個数を$n$，種類数を$k$ としたときに$O(k + n)$ 時間で動く． これまでの研究において，バケットソートに移動コストを加えることで「物理的バケットソート」という枠組みが定義されている． この枠組みにおいては本来のバケットソートの挙動に加え，箱から箱への移動コストも考慮する． すなわち，アイテムを目的の箱に入れるためにはその箱の前に立つ必要があり，$i$番目の箱から$j$番目の箱へ移動する 際にも$|i - j|$ 時間を必要とする．また，アイテムは待ち行列（キュー）の形で与えられており，一番先頭のアイテム から処理していく必要があるが，そのアイテムを即座に目的の箱へ入れるのではなく，アイテム列の最後尾へ後回し にする操作も単位時間で行う事ができる． このモデルの下で，物理的バケットソートの計算量に対する自明な上界として$O(kn)$が考えられる． これまでの研究において，入力を事前に知ることのできない状況下での 物理的バケットソートに対し$O(nsqrt{k})$時間で実現するアルゴリズムが提案されており，これはオーダーレベルで下界と一致している． 一方で，入力を事前に知っている場合においてはこのアルゴリズムは必ずしも最適ではない． 本稿では，入力を事前に知っている条件下での最適アルゴリズムを解明するため， その足掛かりとして種類数$k$を$k=2$に固定した場合での下界解析を行い， ある性質を持つ入力に対して$1.5n$という下界を示した． |
| （英） | Bucket sort is one of the most famous sorting algorithms, and it runs in time $O(k+n)$, where $k$ is the number of buckets and $n$ is the number of items. In this framework, we need a unit time within which to place an item into a bucket. Here, we present a new framework of sorting, emph{physical bucket sort}, where we need time to move from bucket to bucket, we must stand by the bucket, and to move from bucket $i$ to bucket $j$, we need $|i-j|$ units of time in addition to the placing time. It is permitted to postpone an item to the bottom of the pile of items, but it also needs unit time. This is a simple formulation that enables us to sort a pile of reports according to their score. A trivial upper bound of the running time of physical bucket sort is $O(kn)$. It is known that there is an $O(n sqrt{k})$-time algorithm, and it is asymptotically optimal for any non-fixed input. In this talk, we offer the lower bound when the physical bucket sort has only two kinds of items and the input is fixed and known. In this case, we show the lower bound is $1.5n$ for some inputs. |
|
| キーワード | （和） | アルゴリズム / ソートアルゴリズム / バケットソート / 計算量 / / / / |
| （英） | Algorithm / Sort Algorithm / Bucket Sort / Complexity / / / / | |
| 文献情報 | 信学技報, vol. 116, no. 262, COMP2016-26, pp. 23-27, 2016年10月. | |
| 資料番号 | COMP2016-26 | |
| 発行日 | 2016-10-14 (COMP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2016-26 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2016-10-21 - 2016-10-21 |
| 開催地（和） | 東北大学 |
| 開催地（英） | Tohoku University |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2016-10-COMP |
| 本文の言語 | 英語（日本語タイトルあり） |
| タイトル（和） | 2種類のアイテムに限定した物理的バケットソート |
| サブタイトル（和） | |
| タイトル（英） | Physical Bucket Sort with Two Kinds of Items |
| サブタイトル（英） | |
| キーワード(1)（和/英） | アルゴリズム / Algorithm |
| キーワード(2)（和/英） | ソートアルゴリズム / Sort Algorithm |
| キーワード(3)（和/英） | バケットソート / Bucket Sort |
| キーワード(4)（和/英） | 計算量 / Complexity |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 長尾 篤樹 / Atsuki Nagao / ナガオ アツキ |
| 第1著者 所属（和/英） | 電気通信大学 (略称： 電通大) The University of Electro-Communications (略称： UEC) |
| 第2著者 氏名（和/英/ヨミ） | 吉澤 修平 / Shuhei Yoshizawa / ヨシザワ シュウヘイ |
| 第2著者 所属（和/英） | 電気通信大学 (略称： 電通大) The University of Electro-Communications (略称： UEC) |
| 第3著者 氏名（和/英/ヨミ） | 伊藤 大雄 / Hiro Ito / イトウ ヒロオ |
| 第3著者 所属（和/英） | 電気通信大学 (略称： 電通大) The University of Electro-Communications (略称： UEC) |
| 講演者 | 第1著者 |
| 発表日時 | 2016-10-21 13:30:00 |
| 発表時間 | 30分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2016-26 |
| 巻番号（vol） | vol.116 |
| 号番号（no） | no.262 |
| ページ範囲 | pp.23-27 |
| ページ数 | 5 |
| 発行日 | 2016-10-14 (COMP) |
[研究会発表申込システムのトップページに戻る]