整列とは、データを昇順または降順に並べ替えることをいいます。ソート処理とも言います。
【 選択ソート 】
データの先頭から一番小さい値を探し、見つかれば 1 番目のデータと交換する。次に、2 番目以降のデータ列から一番小さい値を探し、2番目のデータと交換する。これを、データ列の最後まで繰り返す(厳密には、データ列の最後より1つ手前までの繰り返しでよい。一つ前まで交換済みであれば、最後(残り)は必ず最大値になるからである)。
もしデータ数が6個であれば(先頭を1番目とする)、とりあえず、最小のデータ(A[w])を1番目(w=1)とする。1番目(A[w])と2番目(A[2])を比較し、2番目のデータの方が小さければ、2番目のデータを最小値(w=2)とする。次に2番目(A[w])と3番目(A[3])を比較して、3番目のデータの方が小さければ、最小値を入れ換える(w=3)、2番目のデータの方が小さければ最小値はそのまま(w=2)。この最小値(A[w])とデータの比較を最後(6番目)まで行うと、最小のデータ(A[w])が見つかる。そのデータと1番目(A[1])を交換する。
つぎに2番目のデータ(A[2])から始め、最小のデータを2番目のデータとする(w=2)。そして、2番目(A[w])と3番目(A[3])を比較し、最小値を探していきデータの最後まで探したら、2番目のデータと交換する。この最小値を探して交換する処理を最後まで繰り返す。
比較回数・・・回
交換回数・・・各ループで最大1回なので、全体では最大 n-1 回
計算量・・・O(n2)
選択ソートのフローチャート(擬似言語)
【 バブルソート(交換法) 】
「バブルソート」とは、その名の通り、隣同士のデータを比較・交換しながら、並び替えを行い、最後までその処理を行うとすべてが並び替わっています。
つまり、起点となるデータ(最後のデータ)と隣である要素数-1のデータの比較から開始して、データの大小が逆転していたら、それぞれのデータを交換し、逆転していなければ、1つずらして比較する。徐々に先頭までデータをずらして比較していき、確定する処理を最後まで繰り返します。
もしデータ数が6個であれば(先頭を1番目とする)、6番目(A[6])と5番目(A[6-1]=A[5])を比較し、大小が逆であれば入れ換える。次に5番目(A[5])と4番目(A[5-1]=A[4])を比較して入れ換える。これを最後まで行うと、最後の1番目(A[1])が最小または最大の数として確定する。再度、後ろ(A[6])から比較していき、確定していない部分について比較していき、確定しない最後(2番目まで)(A[2])まで比較していく。これを最後まで繰り返す。
比較回数・・・回
交換回数・・・元のデータ列によって異なるが、一回のスキャンで平均n/2回なので、全体では平均n(n-1)/4回
計算量・・・O(n2)
バブルソートのフローチャート(擬似言語)
【 マージソート 】
「マージソート」は、既に整列された2個以上の配列を1つの配列に併合する処理を繰り返すことでソートを実現しています。つまり、「分割」して「整列」して「併合」を繰り返します。この方法は、補助記憶装置の大量のデータの並び替えなどに使用される「外部整列法」です。
比較回数・・・n log2 n 回
計算量・・・最大 O(n log n)
マージソートのフローチャート(擬似言語)
【 挿入ソート 】
「挿入法」は、データが整列済みと未整列部分から構成されている場合に有効な方法です。整列済みのデータに未整列のデータを挿入していく方法です。
整列済みのデータの一番後ろのデータと次のデータを最初に比較し、大小の順序が正しければ、次のデータの場所は確定し、整列済みとなります。
2番目(A[1+1])と1番目(A[1])を比較し、大小が逆であれば入れ換える。次に、3番目(A[2+1])のデータと2番目(A[2])のデータを比較し、大小が順序通りなら、3番目のデータの比較終了。もし大小が逆であれば、2番目のデータと3番目のデータを入れ替える。入れ替えた2番目のデータ(元々は3番目のデータ)と左側のデータ(1番目のデータ)とを比較し、大小が逆なら入れ替え、正しければそのままにする。これで3番目のデータの位置が決定される。比較するデータを整列済みのデータのグループの中で正しい順に並ぶように「挿入」していく。(挿入する際、左側のデータを後ろに一つずつずらす。)この操作で、3番目までのデータが整列済みとなる(但し、データが挿入される可能性があるので確定ではない)。つぎに4番目以降のデータについて、整列済みデータとの比較と適切な位置への挿入を繰り返す。4番目のデータと左側のデータを比較して、大小が正しければ、その時点で4番目の位置はそのままの位置で順序通りになる。
比較回数・・・最大回
交換回数・・・元のデータ列によって異なるが、一回のスキャンで平均n/2回なので、全体では平均n(n-1)/4回
計算量・・・O(n2)
挿入ソートのフローチャート(擬似言語)
【 シェルソート 】
「シェルソート」は、ある程度整列されたデータに対して有効である。この方法は、「挿入法」を応用して、一定間隔ごとにデータを振り分け、これを挿入法で整列させて、その間隔を順次、狭くしていく方法です。
シェルソートのフローチャート(擬似言語)
【 クイックソート 】
「クイックソート」は、整列の対象の配列を分割しながら整列を進めます。具体的には、全データから基準値(ピボット)を選び、その値を境にし、より「大きいデータ」と「小さいデータ」のグループになるように振り分けます。この作業を繰り返して行います。また、クイックソートは、「再帰呼出し」と言って、「ある手続きの中から自分自身を呼び出す」方法を用いても実現できます。
注:このアルゴリズムでは、領域の左端の値が領域内で最小かつ同じ値が他の位置に無い場合、ピボットとしてその値を選ぶとループとなってしまう。
比較回数・・・n log2 n 回
計算量 ・・・平均計算量はO(n log n)、最大O(n2)
クィックソートのフローチャート(擬似言語)
【 ヒープソート 】
「ヒープソート」は、「選択法」を応用した方法で、配列を「ヒープ」に変換します。ヒープとは、ルートに最大値が入る時、親ノード≧子ノード(またはルートに最小値が入る時、親ノード≦子ノード)の条件を満たした完全二分木のことを言います。(昇順の場合は、ルートに最小値が入ります。)
この木をヒープの条件を満たすようにする。すなわち全てのノードの子はその親より小さい値になるようにする。 これは
という処理を再帰的に行うことでヒープ構造が生成される。
「ヒープ」とは、以下の条件を満たす「2分木」です。
●完全2分木である。
●root要素が最大値(最小値)を持つ
●どの親子関係でも「親>子または、(親<子)」のような一定の大小関係が成立している。
整列の比較回数は(要素数がn個の時)
平均比較回数・・・ n Log2 n 回
計算量・・・O(n log n)
ヒープソートのフローチャート(擬似言語)
降順に並べ替える場合
探索(サーチ)とは、大量のデータの中から、目的のデータを見つける手続きのことをいう。
【 線形探索法 】
先頭から順番に1つづつデータを探していく方法。リニアサーチや順次探索法ともいう。
線形探索法では、配列データの最後の次に探すデータと同じデータを入れておくことがある。これを番兵という。
番兵は、探す要素が n 個なら n + 1 個目に番兵を入れる。
番兵を使うことで終了判定が容易になる。
こうすることで、検索している値は必ず見つかる。プログラム的には、検索値が見つかるまでとすることができる。
要素数が n 個の場合、平均探索回数は、( n + 1 ) / 2 回となり、最大探索回数は、n 回となる。
線形探索のフローチャート(擬似言語)
【 2分探索法 】
バイナリサーチとも呼ばれる。
順番に整列されたデータのうち中央の要素のデータと探索データを比較し、中央値でデータを2分し、中央値より大きいか小さいかでその前半分のデータか後半分のデータのどちらかを使うか判定する。これを繰り返していく。
先頭から順番に探していく線形探索法より、高速に探すことができる。要素数が n 個の場合、平均探索回数は、log2n 回となり、最大の探索回数は、log2n + 1 回となる。
【 ハッシュ表探索法 】
今までのデータ構造は、基本的にデータの先頭から目的のデータを探す順次探索でしたが、目的のデータが最後の方にあった場合は時間がかかります。そこで、データのキー値やデータ値から計算によってデータを格納する場所を決定し、探索時に同じ計算によって格納場所を見つけるハッシュ法があります。これは直接探索法の1つです。
格納場所の計算のための関数をハッシュ関数といい、その結果をハッシュ値(ハッシュキー)という。
ハッシュ値とデータを格納している表をハッシュ表(ハッシュテーブル)という。
具体的な手法ハッシュ関数を示します。
別々のデータからハッシュで得られる値が同じになってしまうことがあります。これを衝突と言い、先に格納されていたデータをホーム、後のデータをシノニムと言います。衝突の対策を次に示します。
再帰とは、定義や関数の中で自分自身を再度呼び出して利用できる仕組みのことを言う。
再帰を使うと、処理手順が短くなる、プログラムがシンプルになるというメリットがある。
木構造やグラフ理論を使ってデータを探索するための手法。
深さ優先探索、幅優先探索、最短経路探索等がある。
配列に格納されている文字列から特定の文字を探索するアルゴリズムのこと。
文字列から特定の文字列を照合しながら探索するので、文字列照合アルゴリズムとも呼ばれる。
文字列探索には、以下のアルゴリズムがある。
ファイルを処理するためのアルゴリズム。
www.it-shikaku.jp