プログラミングに欠かせないアルゴリズムの種類について

 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を交換、先頭から4番目の要素が確定
  14. ⇒(3, 5, 6, 7, 8, 9) 9と8を交換、5番目、6番目の要素が確定 ★昇順ソート完了★

クイックソート

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

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

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

以上の流れを整理すると次のようになります。

「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)を昇順にソート(配列)する

  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」
  4. ⇒「9」「7」「6」「8」「5」「3」「4」「2」
  5. ⇒「7, 9」「6, 8」「3, 5」「2, 4」
  6. ⇒「6, 7, 8, 9」「2, 3, 4, 5」
  7. ⇒「2, 3, 4, 5, 6, 7, 8, 9」

探索アルゴリズム

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

線形探索

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

二分探索

それに対して、二分探索とは整列されたデータ群を2つのグループに分けて、探索している要素がどちらのグループにあるかの判断を繰り返し、探索範囲を狭めていくとう探索アルゴリズムです。二分探索では整列済みデータの探索に有効であり、整列されていないデータに二分探索を適用する場合は、前述したソートアルゴリズムを使って値を整列させてから二分探索を用います。

アルゴリズムの重要性とは?

プログラミング言語の文法を学習するのに合わせて、アルゴリズムを学ぶ重要性とは何なのでしょうか?それは「計算量の変化」にあります。『アルゴリズムとは?プログラミングをする上でなぜ重要なのか』でも解説していますが、アルゴリズムとはいわば「最良の結果を得るために最も効率的な計算方法」です。

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

プログラミング学習の際は、言語文法だけに着目するのではなく、アルゴリズムの習得にも注力してみましょう。

新規CTA

新規CTA
新規CTA

RELATED POST関連記事


RECENT POST「コラム」の最新記事


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