8. アルゴリズムとデータ構造

8.1. アルゴリズム

8.1.1. アルゴリズムとは

アルゴリズムは問題を解決したり目標を達成するまでの一連の手順のことを指す。 データをどのような単位で扱い、どのようなタイミングで処理するかといったアルゴリズムの工夫により無駄のない効率の良いプログラムを作成できる。

8.1.2. フローチャート

アルゴリズムの作成にはフローチャートを用いて視覚化する。 フローチャートの処理には順次・選択・繰り返しがある。

8.1.3. 変数と代入

変数はプログラムで称する文字や数字を格納する入れ物のこと。 また、変数にデータを入れる処理は代入と呼ばれる。

8.1.4. トレース

トレースは処理を順番にたどって変数の値や実行結果を確認し、プログラムが正しく動作しているか確認すること。

8.1.5. 擬似言語

擬似言語はアルゴリズムを記述する方法でフローチャートのような図形を使わず文章や記号でアルゴリズムを記述する方法。

8.2. 配列

8.2.1. データ構造

データ構造は扱うデータをどのような方法で保持するか決めたもののこと。 主なデータ構造には配列・キュー・スタック・リスト構造・木構造がある。 なおどの構造を用いるかにより処理効率が大きく変わる。

8.2.2. 配列

配列は同じ型のデータの集まりを順番に並べたデータ構造のこと。 配列はデータを整理したり探したりするときによく使用され、データの場所を表す添え字はインデックス、配列データの各入れ物は要素と呼ばれる。

8.3. キューとスタック

8.3.1. キュー

キューは待ち行列が前から順番にさばくように1次元配列で1列に格納されたデータを入れた順番に取り出すデータ構造のこと。 このデータの取り出し方はFIFO(First In First Out)を呼ばれる。 データを入れることはエンキュー、取り出すことはデキューと言われる。

8.3.2. スタック

スタックは最後に入れたデータから先に取り出す、新しいデータから順番に使う構造のこと。 このデータの取り出し方はLIFO(Last In First Out)を呼ばれる。 データを入れることはプッシュ、取り出すことはホップと言われる。

8.4. リスト構造

8.4.1. リスト構造

リスト構造はデータの格納場所が書かれたポインタを使い、離れた場所にあるデータ同士をつないで順番に並べたデータ構造のこと。線形リストや結合リストとも呼ばれる。

リスト構造ではデータとポインタをセットにして扱い、先頭から順にポインタをたどることで各データにアクセスする。 途中のデータ追加や削除が多い処理はリスト構造が配列よりも適している。

リスト構造の特徴

リスト構造ではデータ間をポイントで繋いでいるため、データの追加や削除がポインタだけで済み、要素戸数や位置によらず短期間で処理できる特徴がある。

また、リストの特徴として、ポインタ順にデータをたどるため、配列のように添え字を使い各データに直接アクセスする使い方はできない。

8.4.2. リスト構造の種類

単方向連結リスト

単方向連結リストはデータの後ろにポインタを１つだけ持つリスト構造のこと。

双方向連結リスト

双方向連結リストは前後のデータへのポインタを持つリスト構造のこと。

循環連結リスト

循環連結リストは単方向リストと同じで次のデータへのポインタを持つリストのこと。 単方向リストとの違いは最後尾のデータが先頭データへのポインタを持っているところにある。

8.5. 木構造

8.5.1. 木構造とは

木構造はデータ同紙に階層的な親子関係や主従関係を持たせたデータ構造のこと。OSのファイル管理構成などは木構造になっている。

木構造の各データは節(ノード)、木構造の根っこ部分を根(ルート)、一番下の部分は葉と呼ばれる。また各データは枝でつながっている。

木構造ではデータは親子関係になっており、結ばれた上の節を親、下の節を子と呼ぶ。

8.5.2. 2分木

2分木は根やそれぞれの節から出る枝がすべて２本以下の木のこと。 また、根から葉までの枝の数がすべて一緒の2分木は完全2分木という。

8.5.3. 2分探索木

2分探索木はどの節においても常に「親のデータが左部分木のデータより大きく、右部分木のデータよりも小さい」条件を満たした状態の木(「左<親<右」)のこと。

2分探索木のデータ探索

2分探索木の中にあるデータを最短で探し出すには、探しているデータの根の値を比較する。この探索ではデータが見つかるか、データが見つからず節がなくなるまで繰り返すことでデータを探索できる。

節の追加や削除による2分探索木の再構成

新たな節を追加する場合はデータ探索と同様の方法で正しい地に追加できる。 また、2分探索木から節を削除する場合は節の削除により2分探索木の性質を失わないように、2分探索木を再構成する必要がある。

8.5.4. ヒープ

ヒープは2分木のうち全ての節で「親>子」が成り立つ状態の木のこと。

8.6. 探索アルゴリズム

8.6.1. 探索とは

探索(サーチ)は沢山のデータから目的のデータを見つける事を指す。 データの探索にはデータ構造の特徴にあったアルゴリズムを使う必要があり、代表的なものには線形探索法や2分探索法、ハッシュ探索法がある。

8.6.2. 線形探索法

線形探索法(リニアサーチ)は先頭から順に探索していく方法のこと。 線形探索法では番兵と呼ばれる目的のデータを配列最後尾につけることでフロー処理の簡素化を行える。

特徴は以下の通り。

• 整列されていないデータの探索に向いている
• 総当たり探索になる
• 大量のデータ探索には不向き

なお平均比較回数(平均探索回数)は(n+1)/2回(nはデータ範囲の最大値)となる。

8.6.3. 2分探索法

2分探索法(バイナリサーチ)はあらかじめデータが小さい順か大きい順に整列されている際に使用されるアルゴリズム。手順は以下の通り。

1. データ構造の真ん中のデータを求めているデータと比較する
2. 求めているデータに近い方の範囲(右か左)を絞り込む
3. 絞り込んだ範囲の真ん中のデータと求めているデータを比較する
4. 1から3を繰り返すと求めたいデータが求まる

なお平均比較回数(平均探索回数)はlog2N回(nはデータ範囲の最大値)となる。

8.6.4. ハッシュ探索法

ハッシュ探索法はデータの格納場所のアドレス値をあらかじめ関数を使った計算で決めておくアルゴリズムのこと。また格納先を決めるために用いられる関数はハッシュ関数、ハッシュ関数により求められるアドレスの値をハッシュ値という。

特徴として、衝突(シノニム)が発生しない限りハッシュ探索法では検索データは1回で見つかる。

なお衝突が起こった際は各配列の各要素をリスト構造にして新しい場所に格納する。

8.7. 整列アルゴリズム

データを小さい順(昇順)または大きい順(降順)に並べることは整列と呼ばれる。

8.7.1. 交換法(バブルソート)

バブルソートでは隣接するデータの大小を比較し、必要に応じて入れ替えることで全体を整列させる。

データ比較回数はn(n-1)/2回となる。

def bubble_sort(lst):
    n = len(lst)
    for i in range(n):
        for j in range(n-1):
            if lst[j] >= lst[j+1]:
                lst[j], lst[j+1] = lst[j+1], lst[j]
    return lst

8.7.2. 選択法(選択ソート)

選択ソートでは対象とするデータの中から最小値(or最大値)のデータを取り出し、先頭データと交換しこれを1つずつずらして繰り返すことで整列させる。

データ比較回数はn(n-1)/2回となる。

def selection_sort(lst):
    n = len(lst)
    for i in range(0, n-1):
        min = i
        for j in range(i+1, n):
            if lst[j] < lst[min]:
                min = j
        lst[i], lst[min] = lst[min], lst[i] 
    return lst

8.7.3. 挿入法(挿入ソート)

挿入ソートではデータ列を「整列済みのもの」と「未整列なもの」に分け、未整列の側からひとつずつ整列済みの列の適切な位置に挿入し、全体を整列させる手法。

def insertion_sort(lst):
    for i in range(1, len(lst)):
        tmp = lst[i]
        j = i - 1

        while j >= 0 and lst[j] > tmp:
            lst[j+1] = lst[j]
            j -= 1
        lst[j+1] = tmp
    return lst

8.7.4. 高度な整列アルゴリズム

シェルソート

シェルソートは挿入ソートを改造したもので、ある一定間隔おきに取り出した要素からなる部分列を整列しさらに間隔を詰めて同様の操作を行い、間隔が1になるまで繰り返して整列させる手法。

クイックソート

中間的な基準値を決めてそれよりも大きな値を集めた区分と小さな値を集めた区分に要素を振り分けてこれを繰り返すことで整列する手法。

ヒープソート

未整列データを順序木(ヒープ)に構成し、そこから最大値(or最小値)を取り出して既整列に移す。これを繰り返して未整列部分をなくしていって整列する手法。

8.8. 再帰アルゴリズム

再帰アルゴリズムはある処理を定義した関数Aの中で同じ関数Aを呼び出して処理する再帰呼び出しを用いたアルゴリズムのこと。

8.9. アルゴリズムの実行時間

8.9.1. オーダ記法(O記法)

オーダ記法はアルゴリズムの計算量(実行時間)をO(式) の形で表すこと。

各アルゴリズムのオーダ

平均計算時間≒オーダ