アルゴリズム初学者向けの入門記事です。
主に文系エンジニアを対象に、必要となる数学要素も含めて定期的にまとめていきます。

※私自身、文系エンジニアの初学者なので、ご指導いただいたり切磋琢磨できたりするとめちゃくちゃ嬉しい。

今日の記事は、大枠の整理と数学抜きでも分かりやすいソートを一部見ていきます。(コードあります)
※この記事はHameeアドカレ2019年10日目としても投稿しています

対象読者

・アルゴリズム初学者
・学術的にアルゴリズム勉強してこなかったエンジニア

目次

・アルゴリズムとは
・データ構造とは
・ソートアルゴリズム
　・単純挿入ソート(シャトルソート)
　・クイックソート
・あとがき
・参考文献

アルゴリズムとは

問題を解決するために、明確に定義された規則からなる一連の計算ステップです。

アルゴリズムは、ある値または値の集合を入力として受け取り、値もしくは集合を出力として生成します。例えば、a,bの数字を受け取り、それらを足したa+bを出力する関数もアルゴリズムです。(ただし、計算時間は短かそうだし、複雑さも少なそう)

JIS X0001では以下のように定義されています。

問題を解くためのものであって，明確に定義され，順序付けられた有限個の規則からなる集合。

一見シンプルな定義ですが、アルゴリズムで解くことのできる問題は多岐に渡ります。
例えば、毎日のように使うGoogle検索は探索エンジンを用いて特定の情報が存在するページを素早く発見できるよう、アルゴリズムで課題解決をしています。また、キャッシュレス決済でのクレジットカード情報の暗号化、リソース最適化による経営戦略の補助等、一見アルゴリズムが関わっていないように見える事象も、アルゴリズムによる計算で解くことができるのです。

簡単なWebサービスを作成する場合、アプリケーション層で明示的に複雑なアルゴリズムを必要しない場合があります。しかし、アプリケーション層に限らず高速で動作するクラウド上のサーバや広域ネットワーク、実装に用いたプログラミング言語等、いづれも広範囲に渡ってアルゴリズムが用いられています。

✋(ところで)アルゴリズムの学習は役に立ちますか？

最近のWeb開発では、アプリケーション層でアルゴリズムが必要な時(例えば、地図上で目的地までの最短ルートの算出したい等)、外部サービスやライブラリを使えば解決できる場合は多いと思います。自分たちで実装が不要だとしても、それらがどういったアルゴリズムで答えを求めているのか？を把握した上で選択することは、開発における不確実性を減らす上でとても役立つはずです。
また、携わっている開発やPJにおいて自分たちで実装しないと解決できない課題が発生した時、解決手段となるアルゴリズムを構築する土台として既存のアルゴリズムを理解しておくことは十分に価値がある、と私は考えています。

✋(ちなみに)良いアルゴリズム、悪いアルゴリズムは何で判断しますか？

アルゴリズムの性能を客観的に評価するには計算量が用いられます。計算量は主に時間計算量と領域計算量の2つです。

時間計算量: 実行に要する時間を評価したもの

領域計算量: どのくらい記憶領域やファイル領域が必要であるかを評価したもの

アルゴリズムを構成するプログラムの実行は、それを動作させるハードウェアやコンパイラの前提に依存するため、実行環境のコストを考える必要があります。実行に必要な資源量を予測することを、アルゴリズムを解析すると言います。(初見で「かっこいい！」と思いました)

どうやってアルゴリズムの計算量を求めるの？とか、そもそもアルゴリズムの正しさはどう証明するの？という疑問については、別な記事で深掘りさせてください。

データ構造とは

アルゴリズムの学習をしている際、データ構造の扱いも併せてよく出てきます。データ構造とは、アクセスと更新を容易にする目的でデータを蓄積し組織化する方法です。アルゴリズムを実装する上で、最適なデータ構造が用いられます。

データ構造は目的に応じて使い分けられ、何にでも使える万能なものはありません。そのため、基本的なデータ構造についてはメリット・デメリットを理解しましょう。

文字数増えてきたので詳細は別記事にまとめますが、一般的なWeb開発でもスタックやキューといった単語はよく耳にするかと思います。これらはよく似てはいますが、明確に異なる特徴を持ったデータ構造です。

ソートアルゴリズム

と言うわけで、実例として基礎的なアルゴリズムであるソートを2つ実装してみたいと思います。

ソートアルゴリズムはその名の通り、要素の順番を並び替えるアルゴリズムです。計算機科学における基本的な操作であるため、多くのプログラムは一部にソートを含んでいます。それゆえに優れたソートアルゴリズムは数多く開発されています。

実社会で考えると、図書館の本棚や辞書で活用されています。膨大な数の本は検索しやすいようジャンルや出版年月で順番に整理されますし、辞書の索引の並びがデタラメであれば目的の単語にたどり着くのは非常に効率が悪いです。

ちなみに、実装コードはRubyです。(慣れてない人はごめんなさい...。静的型付けの言語の方が分かりやすかった気がしています...。)
実装にある通り、RubyはArrayなど標準で用意されているクラスを簡単に拡張することができます。今回はArrayクラスにソート済みの新しいオブジェクトを返す関数を追加してみました。

単純挿入ソート(シャトルソート)

挿入ソートは、トランプ遊びで手札のカードを並び替える時に利用する人が多いはずです。テーブルに配られた裏向きのカードを1枚ずつ取り、手持ちのカードの中の正しい位置に挿入していく手法。まさしくこれです。

ソートしていない要素列の先頭の値を、ソート済みの要素列の"適切な位置に挿入する"作業をn-1回繰り返します。

class Array
# 単純挿入ソート
 def shuttle_sort
   # 2番目の要素から最後までを左隣の要素と比較して並び替える
   for j in (1..length-1)
     key = self[j]
     i = j - 1
     # 小さい要素に出会うまで代入する操作を繰り返し、出会えたら小さい要素を先頭方向へ入れ替える
     while i >= 0 && self[i] > key
       self[i+1] = self[i]
       i -= 1
     end
     self[i+1] = key
   end
   self
 end
end

# 実行
arr = Array(1..10).shuffle
p "元の配列"
p arr
p "挿入ソート済みの配列"
p arr.shuttle_sort # => [1,2,3,4,5,6,7,8,9,10]

オーソドックスにイメージしやすく、実装する際もわかり易かったです。
しかし、並び替える要素の個数に依存して計算時間が伸びるため、長いデータの入力を扱う際にはアルゴリズムの効率が悪そうです。(別記事でちゃんと効率計算しましょう)

クイックソート

クイックソートは広く一般的に使われている高速なアルゴリズムです。分割統治を用いて、高速に並び替えます。

一気に全ての値を扱うがために効率が悪いのであれば、小さい単位に分割するのはいかがか？という手法です。分割した部分を再帰的に解き、それぞれの答えをくっつけることで全体の解を導くことができます。

例えば、クイックソートでは基準の値を定め、各要素を基準値と比較して小さいグループと大きいグループに2分割します。それを分割できる最小単位まで繰り返し、結合します。
ここで用いるグループ分けの基準のことを枢軸(すうじく, pivot)と言います。pivotの分割によって計算時間に影響があるので、要素の中央値をとるといったこと検討すべきかもしれません。(ただし、pivotの決定に計算時間を使い過ぎても本末転倒ではあります)

class Array
 def quick_sort
   # 要素を分割していき、要素数が1になった時ソート完了
   return self if length <= 1

   # グループ分けの基準値(枢軸)。クイックソートでは、ピボットより大きい要素の集合と小さい要素の集合に2分割する
   pivot =  slice! length / 2 # 今回は真ん中の要素を枢軸にする

   smallers = []
   biggers = []
   each do |value|
     # pivotと同じ値は小さい集合、大きい集合、のどちらでも大丈夫
     smallers.push value if value <= pivot
     biggers.push value if value > pivot
   end
   push pivot # pivotとなる値を破壊的変更で飛ばしているので戻す。pivotは飛ばしておかないと要素数による分割の判定が完了しない
   smallers.quick_sort + [pivot] + biggers.quick_sort # pivotを二つの分割の間に置く
 end

 # rubyにはEnumerableモジュールに集合を分割するメソッドが定義されているので記述は省略できます。便利
 def _quick_sort
   return self if length <= 1
   pivot = slice! length / 2
   smaller, bigger = partition {|value| value <= pivot }
   push pivot
   smaller.quick_sort + [pivot] + bigger.quick_sort
 end
end

# 実行
arr = Array(1..10).shuffle
p "元の配列"
p arr
p "クイックソート済みの配列"
p arr.quick_sort # => [1,2,3,4,5,6,7,8,9,10]

クイックソートの高速性については、また計測してみましょう。
同じ結果が得られるのであれば、計算時間が短く高速に処理できる方が効率の良いアルゴリズムである、というのもなんとなく想像できたでしょうか。

実装の方法は上記以外にも多岐に渡ると思います！例えば、スタックでインデックスを管理し配列を分割をしてソートすることもできます。

といったところで、実装コードについて改善点等があればぜひ教えてください！

あとがき

ああー、アルゴリズムを学びたい！
テクノロジーで課題を解決していく上で、アルゴリズムは必ず必要と言っても過言ではないのかなと感じています。
私と同じように、学習中のみなさんのお役に立てれば幸いです！分厚い参考書と数式に圧倒されて心が折れそうになった時は、一緒に乗り越えましょう。

記事は今後も書いていくので、よろしくお願いします。
アルゴリズムに限らず、ネットワークやLinux周りも知識を深めていきますのでそちらもいづれ！

参考文献

アルゴリズムイントロダクション 第3版 総合版：世界標準MIT教科書

新・明解 Javaで学ぶアルゴリズムとデータ構造