こんにちは。
今回はアルゴリズムの基礎中の基礎について自分の頭の中を整理するための記事です。
アルゴリズムとは
プログラミングを勉強していなくてもアルゴリズムという言葉を聞くことがありますが、その意味をしっかり説明するのは意外と難しいものです。
アルゴリズムとは簡単にいうと、問題解決に向けた計算や解決方法のことです。
コンピューターにアルゴリズムを通してプログラミングすることで、人間が行うと時間がかかることや不可能なことが可能となります。
アルゴリズムの種類
アルゴリズムにはいくつかの種類があります。
ここではその種類と代表的な使い方の例をあげていきます。
探索アルゴリズム
数多くあるデータの中から目的のデータを探し出すアルゴリズムのことを探索アルゴリズムと言います。
線形探索
データの集合の中からあるデータを探索するために、一つずつデータの確認を行う方法です。
例えば、あるパーティの参加者100人分をまとめたリストがあるとして、その中から寝屋川区出身の五郎さんを探し出すときに、スキップすることなく1から順番にみていきます。
二分探索
整列されたデータの集合を二分し、探し出したい要素が出るまで集合を二分し続ける方法です。
寝屋川の五郎さんが100人の中で78人目の参加者であった場合、50人目の人を区切りにグループを二分します。
五郎さんは50人目より前の集団には存在しないため、51から100人目のグループに存在することがわかります。
つぎにその51から100人目のグループを76人目を区切りに二分します。
するとグループは51から75人目と76人目から100人目に分けられ、五郎さんが属する76から100人目のグループが残ります。
このような作業を繰り返していくことでより効率的に目的であるデータまでたどり着くことができます。
ソートアルゴリズム
データの集合を一定の規則に基づいて順番に並べることをソートと言い、それを可能にする方法をソートアルゴリズムと呼びます。
バブルソート
ソートアルゴリズムの中でも基本的な考え方で、隣り合うデータを比較し規則ごとに並び替えるソートの方法です。
例えば順不同に並んだ1から100人目までのパーティの参加者をソートアルゴリズムで番号順に並び替える場合、隣り合う2人を比べ、番号が「若い人が左にくるように」並べていきます。
つまり「71、34、89、3、・・・」という番号で並んでいた場合、最初の2人は「71、34」となり、若い人が左にくるように並べる規則に従って「34、71」に入れ替えます。
同じように次は「71、89」となりますが、この場合すでに規則に従っているため交換する必要はありません。
「89、3」は規則に反しているため「3、89」と入れ替えられます。
これを順番に行い、規則通りにソートされるまで繰り返すのがバブルソートです。
クイックソート
最も速いとされているソートの方法です。
これは軸となるデータを基にソートしていく方法ですが、文章のみでわかりやすく説明されている記事が見当たらず、自分の言葉でもうまく説明できる自信がないので以下の動画から直感的に理解していただくことを推奨します。
マージソート
パーティの参加者を一列に並べ、それぞれが独立するまで細分化していきます。
ここでは100人を例として持ち上げるとややこしいため、パーティのなかでもバーでお酒を飲んでいる8人を取り出したことにして話を進めます。
例えば「71、34、89、3、11、66、57、98」という8人の参加者がカウンターに座って並んでいたとします。
この全体の集合を2つの集合に分けていく作業を、1人1人が独立するまで続けます。
1. 「71、34、89、3」、「11、66、57、98」
2. 「71、34」、「89、3」、「11、66」、「57、98」
3. 「71」、「34」、「89」、「3」、「11」、「66」、「57」、「98」
次にその細分化したものを倍数で組み合わせていき、規則順に整列させます。
今回は昇順をソートの規則とします。
4. 「34、71」、「3、89」、「11、66」、「57、98」
5. 「3、34、71、89」、「11、57、66、98」
6. 「3、11、34、57、66、71、89、98」
以上のような方法で並び変えるのがマージソートです。
まとめ
今回はアルゴリズムの中でも特に基本として取り上げられる探索アルゴリズムとソートアルゴリズムについて、それぞれの代表的なものをまとめました。
アルゴリズムを初めて勉強する人はぜひ参考にしてみてください。