任意の外部記憶容量で動作するマージソート

山岸 直秀  鈴木 誠  渡辺 重佳  

誌名
電子情報通信学会論文誌 D   Vol.J96-D   No.3   pp.441-451
発行日: 2013/03/01
Online ISSN: 1881-0225
DOI: 
Print ISSN: 1880-4535
論文種別: 特集論文 (学生論文特集)
専門分野: 情報・システム基礎
キーワード: 
マージソート,  In-placeソート,  安定ソート,  空間計算量,  時間計算量,  

本文: PDF(1.5MB)
>>論文を購入


あらまし: 
ソート対象の要素数と等しい外部記憶領域を必要とするマージソートアルゴリズムを,任意の大きさの外部記憶領域で実現できるように改良したアルゴリズムを提案する.同様の改良例は様々に存在するが,本提案はベースアルゴリズムの基本特性をほぼそのまま受け継ぎ,実質的な計算量もほとんど劣化させずに実現した方式である.本論文では,乱数列をソートする実験により有効性の検証も行う.