|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ ー ： [ちょうおん] (n) long vowel mark (usually only used in katakana)
クイックソート (quicksort) は、1960年にアントニー・ホーアが開発したソートのアルゴリズム。分割統治法の一種。 最良計算量および平均計算量はOである。他のソート法と比べて、一般的に最も高速だといわれているが対象のデータの並びやデータの数によっては必ずしも速いわけではなく、最悪の計算量はOである。また数々の変種がある。 安定ソートではない。 == アルゴリズム == # 適当な数（ピボットという）を選択する （この場合はデータの総数の中央値が望ましい） # ピボットより小さい数を前方、大きい数を後方に移動させる （分割） # 二分割された各々のデータを、それぞれソートする 実際にこれを実現するためのアルゴリズムは色々考えられるが、一例を挙げると以下のようなものがある。 # ピボットとして一つ選びそれをPとする。 # 左から順に値を調べ、P以上のものを見つけたらその位置をiとする。 # 右から順に値を調べ、P以下のものを見つけたらその位置をjとする。 # iがjより左にあるのならばその二つの位置を入れ替え、2に戻る。ただし、次の2での探索はiの一つ右、次の3での探索はjの一つ左から行う。 # 2に戻らなかった場合、iの左側を境界に分割を行って2つの領域に分け、そのそれぞれに対して再帰的に1からの手順を行う。要素数が1以下の領域ができた場合、その領域は確定とする。 注：このアルゴリズムでは、領域の左端の値が領域内で最小かつ同じ値が他の位置に無い場合、ピボットとしてその値を選ぶと同じ領域を再帰的に呼び出す無限ループとなってしまう。 ピボットは、通常、データ列からランダムに選んだり、データ列中の適当な三つ程度の数の中央値を選ぶ。このように、ピボットの選び方を工夫することで、最悪計算時間がかかってしまうような入力データ列の可能性を抑える。 また、再帰的にソートする際、対象となるデータの数が少なくなったら、挿入ソートなどの別のアルゴリズムを適用することで高速化する手法が研究されている。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「クイックソート」の詳細全文を読む スポンサード リンク
|