【基本IT知識】探索アルゴリズムとソートアルゴリズムについて

はじめに

アルゴリズムの中でも、特に有名な探索アルゴリズムとソートアルゴリズムについて、改めておさらいしていこうと思います。

 

探索アルゴリズムとは

探索アルゴリズムとは、集合の中からある特定の条件を満たすデータを見つけ出すための手順のことです。

探索アルゴリズムの中でも、最も単純なものは下記の２つのアルゴリズムです。

 

 

線形探索

• 先頭から順に目的のデータを探していく単純な方法

 

二分探索

• データの集合を二分（半分に）しながらデータの探索範囲を狭めていく探索アルゴリズム
• 予めデータが昇順または降順に整列されている場合に使われるアルゴリズム
• まずデータを二等分し、探索範囲の中央値と探索データを比較する
• その後、目的データ範囲を前後半どちらかの部分に絞りこむ作業を繰り返すことで、探索データを見つける

 

 

ソートアルゴリズムとは

ソート用アルゴリズムのソートとは、整列（ソート）のことであり、大量のデータを使いやすいように並び替えるアルゴリズムのことです。

データを小さい順（昇順）または大きい順（降順）に並べることを整列（ソート）といいます。

 

整列アルゴリズムで一般的なのは下記３つです。

 

バブルソート

• 隣接するデータ同士の大小を比較して、その大小の順番が逆であれば交換していくアルゴリズム
• これを繰り返すことで、データを昇順または降順で並べ替える
• データの比較回数は、n(n-1)/2 回行われる

 

選択ソート

• データの中から最小値を探し先頭の値と交換⇒この作業を繰り返して全体を整列させていく

 

挿入ソート

• 整列済みと未整列の２つに分類し、未整列データの先頭の要素を正しい場所に挿入していく

 

木構造とは

アルゴリズムについて、先に記載しましたが、そもそものデータ構造である木構造についても補足として説明します。

木構造とは、データ同士に階層的な親子関係や主従関係を持たせたデータ構造のことです。

 

• 親子関係を持ち、親は複数の子を、子はただ一つの親を持つ
• 図に書き表すと、樹木を逆さにしたような形である
• 木構造の各データを節（ノード、節点）と呼ぶ
• 子のない末端の節を葉、親のない先頭の節を根（ルート）といい、各データは枝で繋がっている
• 親の左の子についている枝、節、葉をまとめて左部分木といい、右についている枝、節、葉をまとめて右部分木という

 

木構造には、枝や節の付き方で様々な種類があるため、順番に記載していきます。

 

二分木

 

根やそれぞれの節から出る枝が、すべて２本以下の木を二分木といいます。

二分木の中でも根から葉までの枝の数がすべて一緒の二分木を、完全二分木といいます。

 

また、二分木に対して、子が３つ以上ある節を持つ木を多分木といいます。

 

二分探索木

 

二分探索木については、記事や書籍で調べてみるとこのように書かれていました。

二分探索木（にぶんたんさくぎ、英: binary search tree）は、コンピュータプログラムにおいて、「左の子孫の値 ≤ 親の値 ≤ 右の子孫の値」という制約を持つ二分木である。探索木のうちで最も基本的な木構造である。

https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2%E6%9C%A8

 

２文木のうち、どの節においても、常に「親のデータが左部分木のデータより大きく、右部分木のデータよりも小さい」（左部分木＜親＜右部分木）という条件を満たした状態の木を２分探索木といいます。

かんたん合格　基本情報技術者教科書　令和２年度版

 

さいごに

どうでしたでしょうか？

今回ご紹介したアルゴリズムは基本情報技術者などの資格試験でも出題される概念ですので、理解しておくといいと思います。