基本情報技術者試験(FE)

アルゴリズムとプログラミング

ソート(整列)

ソート(整列)
データ群を一定の規則に従って並び替える処理をソート(整列)という。
 

バブルソート(基本交換法)

隣り合う値を大小比較して大小の順序が逆であれば入替る。全ての配列分繰り返すことでソート(整列)させるアルゴリズム。

バブルソート(昇順例)

配列番号
データ群

比較1巡目









比較2巡目





比較3巡目


比較4巡目

以上の例は昇順の為、比較一巡目が完了した時点で配列番号5の値は最大値として確定し、 比較2巡目の配列番号5の比較は不要となる。以降同様に比較と入替を行う。
n個の配列に対する比較回数はn(n-1)/2回、計算量はO(nとなる。

 

選択ソート(単純選択法)

データ群の中から最小値もしくは最大値を検出して最初の配列と入れ替える。次に最初の配列以外を対象として同処理を行う。全ての配列分繰り返すことでソート(整列)させるアルゴリズム。

選択ソート(昇順例)


配列番号
データ群







初期配列
比較1巡目
最小配列


最小配列

最小配列


最小配列

入替










初期配列
比較2巡目
最小配列

最小配列

最小配列

入替









初期配列
比較3巡目
最小配列

最小配列

入替








初期配列
比較4巡目
最小配列

入替


比較1巡目は配列番号1を起点に他の配列と比較して最小値の配列を特定し、配列番号1と入れ替える。 以降同様に、比較2巡目は配列番号1を除いた配列番号2を起点に他の配列と比較といった様に順次比較を行う。
n個の配列に対する比較回数はn*(n-1)/2回、計算量はO(nとなる。

※バブルソートと比べ、比較回数は同数ではあるがデータ入替回数が少ない為、処理時間が速くなる。 データ入替回数はn-1回(バブルソートは平均n(n-1)/4回)となる。

 

マージソート

データ群を配列の最小単位まで分解後、隣り合う値を昇順もしくは降順でのマージ(併合)を繰り返すことでソート(整列)させるアルゴリズム。

マージソート(昇順)


配列番号
データ群

分割1回目




分割2回目



分割3回目



併合1回目



併合2回目




分割4回目




併合3回目




併合4回目

通常、分割の単位は2分割とし、以上の様な再帰呼び出しにより分割と併合を繰り返す。 (必ずしも再帰処理にする必要はない。)
n個の配列に対する比較回数はnlog回、計算量はO(nlogn)となる。


※処理中、記憶領域を比較的多く消費する。

※処理速度の速いアルゴリズムとされている。(バブルソートや選択ソートと比較すると速い)

関連資格
  • 公務員
  • 行政書士
  • 司法書士
  • 宅建
  • 不動産鑑定士
  • 公認会計士
  • 土地家屋調査士
  • ビジ法
  • FP
  • 中小企業診断士
  • マン管
  • 前のページに戻る
ページのトップへ戻る