ソートアルゴリズム・探索アルゴリズムとは?|アルゴリズム学習のはじめの一歩!

 2020.03.23  株式会社システムインテグレータ

アルゴリズムとは「何らかの問題を解決するために考えらえた手順や計算方法」のことです。アルゴリズムを習得することで、日常生活や業務の中での問題解決に役立てることができたり、特にプログラミング能力の向上には大きく寄与します。アルゴリズムとは何かに関しては以下のブログをご覧ください。
 【ブログ】アルゴリズムとは?プログラミングをする上でなぜ重要なのか

本記事では、まずはじめに知っておきたい具体的なアルゴリズムの種類について、ソートアルゴリズムと探索アルゴリズムの例をもとに解説します。

ソートアルゴリズム

アルゴリズムの中で最も基本的なものが「ソート(整理、並べ替え)」です。データベースをはじめ、大量のデータを扱う機会は少なくありません。その際に、データを昇順、降順など、一定の規則に従って整列させる必要があります。そのための技術がソートアルゴリズムです。ここでは代表的なソートアルゴリズムとして、「バブルソート」「クイックソート」「マージソート」を紹介します。

バブルソート

データの末尾より隣接する値の比較の入れ替えを繰り返すことで、整列させる方法をバブルソートと呼びます。

例)(9, 7, 6, 8, 5, 3)を昇順にソート(配列)する

  1. (9, 7, 6, 8, 5, 3) この並び順でスタート
  2. (9, 7, 6, 8, 3, 5) 5と3を交換
  3. (9, 7, 6, 3, 8, 5) 8と3を交換
  4. (9, 7, 3, 6, 8, 5) 6と3を交換
  5. (9, 3, 7, 6, 8, 5) 7と3を交換
  6. (3, 9, 7, 6, 8, 5) 9と3を交換、先頭要素が確定
  7. (3, 9, 7, 6, 5, 8) 8と5を交換
  8. (3, 9, 7, 5, 6, 8) 6と5を交換
  9. (3, 9, 5, 7, 6, 8) 7と5を交換
  10. (3, 5, 9, 7, 6, 8) 9と5を交換、先頭から2番目の要素が確定
  11. (3, 5, 9, 6, 7, 8) 7と6を交換
  12. (3, 5, 6, 9, 7, 8) 9と6を交換、先頭から3番目の要素が確定
  13. (3, 5, 6, 7, 9, 8) 9と7を交換、先頭から3番目の要素が確定
  14. (3, 5, 6, 7, 8, 9) 9と8を交換、5番目、6番目の要素が確定 ★昇順ソート完了★

このような手順によって数値を配列していくものをバブルソートと呼びます(並べ替えの過程で数字が右から左へ移動していく様子が、泡(バブル)がフワフワと浮かんでいくように見えることから名づけられたそうです)。

クイックソート

上記のバブルソートよりも高速な値の整列を実現するアルゴリズムがクイックソートです。このアルゴリズムでは、ピボットと呼ばれる基準値を決め、データ群を基準以上と基準未満の2つのグループに分割し、処理を繰り返すことで要素を入れ替えていきます。

例)(5, 9, 8, 3)を昇順にソート(配列)する
ピボット(基準値)の決め方は一通りではありませんが、今回は「先頭の2つの値のうち大きい値を選ぶ」というルールで実施してみます。

  1. 先頭の異なる2つの値に着目すると5と9があり、そのうち大きい値となる9をピボットとして取ります。先頭から9以上の値を探索すると9(先頭から2番目の要素)が見つかり、末尾から9未満の値を探索すると3(末尾の要素)が見つかります。そこで9と3を交換して、「5, 3, 8, 9」と整列します。
    5   9  8  3  ⇒  5  3  8  9
  2. 先頭から3番目以降の要素から9以上の値を探索すると9が見つかり、末尾から2番目以降の要素から9未満の値を探索すると8が見つかります。ただし、探索位置が交差してしまったため、探索位置が交差した8と9の間で数列を分割して「5, 3, 8」「9」と整列します。このように数列を分割することで、1つの数列を基準値未満のグループ「5, 3, 8」と基準値以上のグループ「9」に分割されました。
    「5, 3, 8, 9」 ⇒ 「5, 3, 8」「9」
  3. 「5, 3, 8」の中で5をピボットに取り、先頭から探索して見つかった5と、末尾から探索して見つかった3を交換して「3, 5, 8」と整列します。
    5, 3, 8」「9」 ⇒ 「3, 5, 8」「9」
  4. さらに探索を続けると3と5の探索位置が交差したので、「3」「5,8」を分割します。
    「3, 5, 8」「9」 ⇒ 「3」「5, 8」「9」
  5. 「5, 8」にて8をピボットに取り、探索位置が交差する5と8の間で分割して「5」と「8」となります。
    「3」「5, 8」「9」 ⇒ 「3」「5」「8」「9」

以上の流れを整理すると次のようになります。
「5, 9, 8, 3」
⇒「5, 3, 8, 9」
⇒「5, 3, 8」「9」
⇒「3, 5, 8」「9」
⇒「3」「5, 8」「9」
⇒「3」「5」「8」「9」

マージソート

マージソートとは、データの分割を繰り返すことで、バラバラになった要素を順序に注意しながら併合(マージ)していきます。処理時間がデータの並びに大きな影響を受けないのが特徴です。

例)(9, 7, 6, 8, 5, 3, 4, 2)を昇順にソート(配列)する

初期値 「9, 7, 6, 8, 5, 3, 4, 2」
分解1 「9, 7, 6, 8」「5, 3, 4, 2」
分解2 「9, 7」「6, 8」「5, 3」「4, 2」
分解3 「9」「7」「6」「8」「5」「3」「4」「2」
併合1 「7, 9」「6, 8」「3, 5」「2, 4」
併合2 「6, 7, 8, 9」「2, 3, 4, 5」
併合3 「2, 3, 4, 5, 6, 7, 8, 9」 

探索アルゴリズム

データベースに格納されている大量のデータの中から、条件に一致した値を効率良く見つけるためのアルゴリズムが「探索アルゴリズム」です。主に、「線形探索」と「二分探索」というアルゴリズムがあります。

線形探索

線形探索とは、先頭のデータから条件に照らし合わせながら調べていく探索アルゴリズムを指します。シンプルな方法ではありますが、探している値がデータベースの最後の要素であった場合、すべての要素を探索しなければいけないため手間がかかるというデメリットがあります。

二分探索

それに対して、二分探索とは整列されたデータ群を2つのグループに分けて、探索している要素がどちらのグループにあるかの判断を繰り返し、探索範囲を狭めていくとう探索アルゴリズムです。

二分探索では整列済みデータの探索に有効であり、整列されていないデータに二分探索を適用する場合は、前述したソートアルゴリズムを使って値を整列させてから二分探索を用います。これは、複数のアルゴリズムを組み合わせて使う場合の良い例ですね。

プログラミングにおけるアルゴリズムの重要性とは?

アルゴリズムを学ぶ重要性とは何なのでしょうか?
プログラミングを例にあげるとすれば、それは「計算量の変化」にあります。この記事からもアルゴリズムを使うことで計算量を削減できること、どのアルゴリズムを選択するかによっても計算量が異なってくることを感じて頂けたならうれしいです。

さらに具体的な仕事の場面で考えると、システム開発では膨大なプログラムを必要とするため、1つ1つに効率的なアルゴリズムを適用することで、全体のパフォーマンスを大幅に向上できる利点があります。このため、プログラマーの資質として「アルゴリズムへの理解度」も問われるのは至極当然のことです。

プログラマーはもちろん、プログラミングをしない人もより効率的、効果的な業務のためにアルゴリズム学習を進めてみることをオススメします。

新規CTA

新規CTA
新規CTA

RELATED POST関連記事


RECENT POST「アルゴリズム」の最新記事


この記事が気に入ったらいいねしよう!