講演抄録/キーワード |
講演名 |
2016-04-22 14:30
物理的バケットソート ヤコノ ジョン(ニューヨーク大)・伊藤大雄・○長尾篤樹・西野順二(電通大)・ラパポート デイビッド(クイーンズ大) COMP2016-5 |
抄録 |
(和) |
バケットソートとは最も有名なソートアルゴリズムの一つであり,ソートの対象となるアイテムの個数をn,種類数をk としたときにO(k + n) 時間で動く.本稿では,バケットソートに移動コストを加えることで「物理的バケットソート」という枠組みを定義する.バケットソートにおいてはアイテム一つを目的の箱に入れることが定数時間でできるという前提で行われているが,物理的バケットソートにおいては箱から箱への移動コストも考慮する.すなわち,アイテムを目的の箱に入れるためにはその箱の前に立つ必要があり,i 番目の箱からj 番目の箱へ移動する際にも|i - j| 時間を必要とする.また,アイテムは待ち行列(キュー)の形で与えられており,一番先頭のアイテムから処理していく必要があるが,そのアイテムを即座に目的の箱へ入れるのではなく,アイテム列の最後尾へ後回しにする操作も単位時間で行う事ができる.この簡潔なモデルで書類の山に対する仕分け等に必要な時間を上記コストの合計で定式化することができる.物理的バケットソートの計算量に対する自明な上界としてO(kn) が考えられる.本稿では物理的バケットソートをO(n√k) 時間で実現するアルゴリズムを提案する.さらに,ある箱の中に置いたアイテム全てを単位時間で回収することができるモデル(このモデルを「トレイモデル」,前者のモデルを「ポストモデル」と呼ぶ)を考え,このモデルに対するO(n log k) 時間アルゴリズムを与える,さらにこの二つのモデルの計算時間はどちらもオーダーの意味で下界値であることを示す. |
(英) |
Bucket sort is one of the most famous sorting algorithm, which runs in O(k + n)-time where k is the number of buckets and n is the number of items. In this framework, we need a unit time to put an item into a bucket. In this report, we present a new framework of sorting, “physical bucket sort,”where we need a moving time: to put an item into a bucket we must stand by the bucket and to move from bucket i to bucket j, we need |i- j|-time, in addition to the putting time. To postpone an item to the bottom of the pile of items is allowed, but it also needs a unit time. This is a simple formulation of sorting a pile of reports by their score. A trivial upper bound of the running time of physical bucket sort is O(kn). In this report, we show an O(n√k)-time algorithm and prove it the best possible. We also consider another model in which an operation to pick-up all items in a bucket
by paying a unit time is allowed. In the second model, we show an O(n log k)-time algorithm and prove that it is the best possible also. |
キーワード |
(和) |
アルゴリズム / ソートアルゴリズム / バケットソート / 計算量 / / / / |
(英) |
Algorithms / Sort Algorithms / Bucket Sort / Complexity / / / / |
文献情報 |
信学技報, vol. 116, no. 17, COMP2016-5, pp. 29-34, 2016年4月. |
資料番号 |
COMP2016-5 |
発行日 |
2016-04-15 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2016-5 |