プログラミングの勉強に欠かせないアルゴリズムとは？アルゴリズムの種類

ソートアルゴリズム

データベースを始めとして、プログラミングでは大量のデータを取り扱うケースが頻発します。その際、昇順（値を小さい順に並べる）や降順（値を大きい順に並べる）など、記憶領域に格納されたデータを一定の規則で整列（ソート）させる作業に用いられるアルゴリズムが「ソートアルゴリズム」です。

ソートアルゴリズムにはさまざまな種類がありますが、代表的なアルゴリズムとして「バブルソート」「クイックソート」「マージソート」の3種類が挙げられます。

バブルソート

バブルソートは、データの末尾から隣接する要素の比較・入れ替えを繰り返すことでソートする方法です。

【例】｛10, 7, 6, 8, 5, 4｝を昇順にソート

｛10, 7, 6, 8, 5, 4｝
→｛10, 7, 6, 8, 4, 5｝（5と4を交換）
→｛10, 7, 6, 4, 8, 5｝（8と4を交換）
→｛10, 7, 4, 6, 8, 5｝（6と4を交換）
→｛10, 4, 7, 6, 8, 5｝（7と4を交換）
→｛4, 10, 7, 6, 8, 5｝（10と4を交換、先頭要素が確定）
→｛4, 10, 7, 6, 5, 8｝（8と5を交換）
→｛4, 10, 7, 5, 6, 8｝（6と5を交換）
→｛4, 10, 5, 7, 6, 8｝（7と5を交換）
→｛4, 5, 10, 7, 6, 8｝（10と5を交換、先頭から2番目の要素が確定）
→｛4, 5, 10, 6, 7, 8｝（7と6を交換）
→｛4, 5, 6, 10, 7, 8｝（10と6を交換、先頭から3番目の要素が確定）
→｛4, 5, 6, 7, 10, 8｝（10と7を交換、先頭から4番目の要素が確定）
→｛4, 5, 6, 7, 8, 10｝（10と8を交換、先頭から5番目、6番目の要素が確定）

クイックソート

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

基準値の取り方はさまざまですが、今回は先頭の異なる2つの値のうち、大きい値を基準値に取ることにします。

【例】｛4, 8, 7, 3｝を昇順にソート

1. 先頭から見ていくと、異なる2つの値4と8があるので、8を基準値に取ります。先頭から8以上の値を探索すると8（先頭から2番目の要素）、末尾から8未満の値を探索すると3（末尾の要素）が見つかります。そこで、8と3を交換して、｛4, 3, 7, 8｝とします。

2. 探索を続けます。左から（先頭から3番目以降の要素を）探索すると8、右から（末尾から2番目以降の要素を）探索すると7が見つかりますが、探索位置が交差しています。そのため、探索位置が交差した7と8の間で数列を分割して、｛4, 3, 7｝｛8｝とします。

このようにすることで、1つの数列を基準値未満のグループ｛4, 3, 7｝と基準値以上のグループ｛8｝に分割することができました。

3. ｛4, 3, 7｝について、基準値を4に取ります。先頭から探索して見つかった4と末尾から探索して見つかった3を交換すると、｛3, 4, 7｝となります。さらに探索を続けると、探索位置が3と4の間で交差するため、｛3｝｛4, 7｝と分割します。

4. ｛4, 7｝について、基準値を7に取ります。探索位置が交差する4と7の間で分割して、｛4｝｛7｝とします。

上記の内容を整理すると、以下のようになります。

｛4, 8, 7, 3｝
→｛4, 3, 7, 8｝
→｛4, 3, 7｝｛8｝
→｛3, 4, 7｝｛8｝
→｛3｝{4, 7}｛8｝
→｛3｝｛4｝｛7｝｛8｝

マージソート

マージソートは、データの分割を繰り返し、バラバラにした要素を順序に注意しながらマージ（併合）します。処理時間がデータの並びに大きな影響を受けない点が魅力です。

【例】｛8, 4, 5, 7, 2, 1, 3, 6｝を昇順にソート

｛8, 4, 5, 7, 2, 1, 3, 6｝
→｛8, 4, 5, 7｝｛2, 1, 3, 6｝
→｛8, 4}｛5, 7｝｛2, 1｝｛3, 6｝
→｛8｝｛4｝｛5｝｛7｝｛2｝｛1｝｛3｝｛6｝
→｛4, 8｝｛5, 7｝｛1, 2｝｛3, 6｝
→｛4, 5, 7, 8｝｛1, 2, 3, 6｝
→｛1, 2, 3, 4, 5, 6, 7, 8｝

探索アルゴリズム

大量のデータの中から条件に合致した目的の要素を効率良く見つけるためには、「探索（サーチ）アルゴリズム」が欠かせません。主な探索アルゴリズムには「線形探索」と「二分探索」があります。

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

一方の二分探索では、整列されたデータ群を2つのグループに分け、探している要素かどちらのグループにあるか判断することを繰り返し、検索範囲を狭めていきます。

二分探索は、整列済みデータの探索に効果を発揮します。整列されていないデータに二分探索を適用する場合は、ソートアルゴリズムで整列してから二分探索を用います。

アルゴリズムの重要性と勉強法

プログラミングでは大量のデータを取り扱う場面が多く発生します。大量のデータを効率良く活用するためには、アルゴリズムを知識として理解するだけではなく、コーディングしてみることが欠かせません。

アルゴリズムの原理を理解した後はサンプルプログラムのコードに1行ずつ目を通し、具体的にどのような処理がされているかを確認してください。

なぜ、アルゴリズムが重要なのでしょうか。それはアルゴリズムの選び方によって計算量が変わるためです。大量のデータを並び替える際、ソートアルゴリズムを知っていれば、クイックソートでデータを素早くソートできることを思いつくでしょう。

ただし、データがある程度順序良く並んでいる場合、大きな効果を得られないため、他のアルゴリズムを選択する方法もあります。

また、クイックソートは安定なソートではない点にも注意が必要です。安定なソートとは、同等なデータが並んだデータ群をソートしたとき、整列前の順序が保たれることを指します。

例えば、学生番号とテストの点数が対になった成績データを、点数順に並び替えることを考えましょう。安定なソートを用いれば、同じ点数の学生は学生番号順に並びます。しかし、安定でないソートの場合、同じ点数の学生が学生番号順に並ばない可能性があるのです。

プログラミングに慣れていない方にとっては、アルゴリズムはとっつきにくい部分がありますが、一度マスターしてしまえば、使いこなせるようになります。プログラムを書いて動くことを確認できた後は、より効率の良いプログラムが書けないか考えてみましょう。

プログラミング系 人気コースランキングTOP3

1. プログラマー入門コース
2. プログラマーコース
3. ITエンジニア総合コース

おわりに

技術革新が激しいIT・Web業界では、次々と新しい技術が生まれます。これは、プログラミング言語についても例外ではありません。最近では人工知能やデータ分析の盛り上がりに伴い、PythonやRのような言語も注目され始めています。

しかし、将来どのような言語を利用することになっても、プログラミングの根底にあるアルゴリズムをしっかりと学んでおけば、スムーズに移行できるはずです。

アルゴリズムも含めて基礎からプログラミングを学びたい方は、ITやWebの専門スクールに通うことをおすすめします。インターネット・アカデミーのプログラミング講座では、プログラミング初心者の方でも、修了後には設計を考えながらプログラミングできるようにカリキュラムが組まれています。ご興味のある方は、お気軽に無料体験レッスンにご参加ください。