アルゴリズムとは?意味をわかりやすく解説!

みなさん「アルゴリズム」って言葉聞いたことがありますか?

小さいころ、「アルゴリズム体操」という子供向け番組でよく流れていた体操にはまっていました。

こんにちは。大学に通いながらブログを書いている今井@ima_maru)です。

私が最初アルゴリズムという単語を調べたのは、大学の授業を選択するときでした。

「アルゴリズムって何?」「学ぶと何がいいの?」と思ったのがきっかけです。

この記事を見ている方は、

  • プログラミングにおいてのアルゴリズムとは何なのか?
  • そもそもアルゴリズムってどういう意味?
  • いいアルゴリズムって?

このような疑問をお持ちの方ではないでしょうか?

今回の記事は、プログラミングで重要な「アルゴリズム」についてわかりやすく解説していこうと思います。

アルゴリズムの意味

アルゴリズム(algorithmは日本語に訳すと、演算法算法などと呼ばれます。

プログラミングにおけるアルゴリズムの意味は、「問題を解くための計算方法」です。

なので、イメージは難問を解くときの考え方とかに近いです。

数学の勉強でいえば、「この公式を使うと速く解けるよ」とかありますよね?

そういうことがプログラミングにもあるわけです。

プログラミングにおいては、アルゴリズムはある程度形が決まっています。

形が決まっているとは、「この問題にはこういうやり方が一番効率的である」とか、「この問題はこうやってやれば解ける」とかそういうことです。

皆さんが考えるより前に、天才的な人たちが考えた正攻法があるはずです。

今回は例として2つアルゴリズムの問題を用意しました。

  1. ソーティングアルゴリズム
  2. 探索アルゴリズム

それぞれについて少し掘り下げてみようと思います。

ソーティングアルゴリズム

プログラミングには、ソーティング問題というものがあります。

ソーティング(sorting:整列)とは、与えられたデータをある基準に従って順に並べなおすことです。

例えば、1~10の整数がばらばらに並べられているデータがあったとしたら、それを小さい順に「1,2,3…9,10」に並べなおすことがソーティングということです。

ソーティング問題とはこれを「どういう風に考えれば効率よく処理できるか」ということを考える問題で、その考えや手法がソーティングアルゴリズムです。

基本的なソーティングアルゴリズム3選

基本的なソーティングアルゴリズムは、以下の3つを紹介します。

  • 選択ソート(Selection Sort)
  • 挿入ソート(Insertion Sort)
  • バブルソート(Bubble Sort)

選択ソート(Selection Sort)

選択ソートとは、要素から最大値or最小値を探索し取り出していくソーティングアルゴリズムです。

基本的なソートの一つですが、大規模なソートになると極端に遅くなります

挿入ソート(Insertion Sort)

挿入ソートとは、整列してある要素に追加要素を適切な場所に挿入するソーティングアルゴリズムです。

これも基本的なソートの一つですが、大規模なソートになると極端に遅くなります

バブルソート(Bubble Sort)

バブルソートとは、隣り合った要素を比較し整列を行うソーティングアルゴリズムです。

泡が浮いてくるように見えるのがバブルソートといわれる所以です。

これも基本的なソートの一つですが、大規模なソートになると極端に遅くなります

とても速い有名なアルゴリズム3選

ここからは、先ほどの基本的なソートとは違い、大規模なソートにも適しているソーティングアルゴリズムを3つ紹介します。

とても速い有名なソーティングアルゴリズムは、以下の3つを紹介します。

  • クイックソート(Quick Sort)
  • ヒープソート(Heap Sort)
  • マージソート(Merge Sort)

クイックソート(Quick Sort)

クイックソートとは、ある一要素を基準にして「その値より小さいか大きいかで分ける」という処理を繰り返し行うソーティングアルゴリズムです。

これが一番有名なソートだと思います。

そしてとても速いソーティングアルゴリズムです。

ヒープソート(Heap Sort)

ヒープソートとは、ヒープというデータ構造を使ったソーティングアルゴリズムです。

ヒープは最大値or最小値の要素が一番先頭に来るという特徴を持っています。

このヒープ構造を作り、その構造を保ちながら最大値or最小値を取り出していきます。

これもとても速いソーティングアルゴリズムです。

マージソート(Merge Sort)

マージソートとは、整列済みの要素を合併(マージ)して大きくしていくソーティングアルゴリズムです。

合わせるときに、それぞれが整列済みという特徴を利用した工夫がなされています。

これもとても速いソーティングアルゴリズムです。

ソーティングアルゴリズムに関する参考サイト

今紹介したソーティングアルゴリズムはこちらの記事でわかりやすく紹介されています。

参考 【Unity】ソートアルゴリズム12種を可視化してみた - Qiita

また大規模なデータで行ったソートを可視化した動画が有名です。

上に書いてあるのは、ソート名 – 比較回数, 配列へのアクセス回数, 速度(小さいほど速くしている)だと思います。

結局どのソート方法も同じ結果になるはずなんですが、比較回数や交換回数を調べると全然、処理数が違うことがわかるんです。

1秒でできるソート方法と1分かかるソート方法だったら前者のほうがいいわけです。

ほかにも「こんな時にはうまくいかない」「特定の状況では一瞬でできる」なんてこともあり、プログラマはこれらを加味してどのソーティングアルゴリズムが適しているか見極めないといけません。

このように、ソーティングのやり方、考え方次第では処理を重くしてしまったりするわけです。

アルゴリズムとはまさにこのやり方、考え方を指します。

探索アルゴリズム

探索とは、与えられたデータの中から、目的のデータxを見つけることを言います。

例えば、図書館の索引簿から本を探したり、辞書を引いたりすることなどは探索の一種です。つまり、

探索とは、データ集合や情報源から何らかの特徴(キー)を用いて、それに対応するデータや情報を探し出すことである。

と言えます。

辞書を引くときのアルゴリズム

辞書で「探索」という単語を引くことを想像してください。

普通でしたら、「あ→い→う→…→そ→た」と飛んで、「たん」「たんさ」「探索」と見つけていくはずです。

もしくは、「ち」から戻って「探索」を引いたほうが早いかもしれません。

これらは、普段皆さんが当たり前のようにやっていることですが、コンピュータにとっては当たり前ではありません

コンピュータで辞書を引くとき、単語を見つける際にプログラムに基づいて探索します。

このプログラム次第では何時間もかかったり、一瞬で終わったりします。

何時間もかかるような例としては、最初の単語から一単語、一単語、照合していくというのがいい例です。

皆さんが当たり前のようにやっている、「頭文字の部分まで飛んで…」というのがありませんから、辞書の最後の「ん」に近ければ近い程、相当な時間を要します。

これは、辞書が50音順になっていることをまったく活用していないのが原因です。

アルゴリズム的に言えば、私たちが普段行っている辞書の引き方は、文字列パターン照合という形になり

  1. 「た」まで飛ぶ
  2. 「たん」まで飛ぶ
  3. 「たんさ」まで飛ぶ
  4. 「探索」を見つける

というアルゴリズムになっています。

このように、どちらの方法でも結果的には探し出すことができるはずです。

ですが、明らかに楽さが変わります。

探し方を工夫するだけで、手間が省けます。

この「探し方」こそが「アルゴリズム」なんです。

アルゴリズムとは「問題を解くための計算方法」と言いましたが、まさしくこれのことを指しています。

方法です。やり方手法考え方。そんな感じです。

良いアルゴリズムとは?

アルゴリズムを工夫すれば、問題を簡単に解けたりするんです。つまりは、処理を少なくすることができるということです。

プログラミングにおいてのアルゴリズムとは、とても重要な役目で、アルゴリズムが良いと演算が早く終わったり、アルゴリズムが悪いと動作が重くなったり、時にはフリーズしたりと。 

良いアルゴリズムの特徴は、

  • 計算量が少なくて済む
  • メモリをあまり使わない(作業スペースが少なくて済む)
  • 安定性があり、最悪のケースにも備えている

ということがあげられます。

計算の際に使うメモリ、要はスペースがいかに小さいかってのも良いアルゴリズムの評価の一つです。

また、時にはうまくいかない方法であったり、フリーズするようなことがあるのは、安定性の面でいいアルゴリズムとは呼べません。

プログラミング言語を将来性からランキングで紹介!【2019年最新版】

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です