著者

溝井 直史 尾崎 俊治

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会論文誌. A, 基礎・境界 (ISSN:09135707)

巻号頁・発行日

vol.78, no.9, pp.1142-1148, 1995-09-25

参考文献数

8

被引用文献数

4

---

クイックソートはアルゴリズムにおいてよく知られたソーティングアルゴリズムである.このアルゴリズムは分割統治法に基づいている.ソートすべき配列を,その中のある一要素の値より大きな値の集合と小さな値の集合の二つに分割して,それぞれの部分を独自にソートする.この操作は分割された各部分に対して再度繰り返されるので,このアルゴリズムは再帰的な構造をもつ.クイックソートの平均の時間計算量(平均比較回数)はO(n log n)である.但し,ソートすべきデータによっては性能が極端に悪くなる場合があり,最悪の時間計算量はO(n^2)である.本論文では,まず,クイックソートの時間計算量に基づいた母関数を導入し,これを利用して解析的に時間計算量の平均と分散を求める.そして,この平均と分散を利用して,クイックソートの時間計算量の分布が正規分布で近似できるか,カイ2乗適合度検定を行う.更に,クイックソートの時間計算量の分布を3母数ワイブル分布で近似することにより,時間計算量がある値xを超える確率R(x)を精度良く算出する手法を提案する.最後に,ソーティングアルゴリズムの選択に関する考察を行う.