アルゴリズム

アルゴリズムの比較

通常、問題を解決する方法は1つだけではありません。ある料理を作るのに、見た目は違っても最終的には同じ味になるようなレシピがたくさんあるかもしれません。アルゴリズムも同じです。しかし、これらの方法の中には、他の方法よりも優れたものがあります。もしレシピが、あなたが持っていないような複雑な材料をたくさん必要とするなら、それはシンプルなレシピほど良いものではありません。問題を解く方法としてアルゴリズムを見るとき、しばしば、あるアルゴリズムを使って問題を解くのにコンピュータがどれくらいの時間を要するかを知りたくなる。私たちがアルゴリズムを書くとき、できるだけ早く問題を解決できるように、アルゴリズムには最小限の時間しかかからないようにしたいものです。

料理でも、完成までに時間がかかったり、把握すべきことが多かったりして、難しいレシピがあります。アルゴリズムも同じで、コンピュータにとってやりやすい方が良いアルゴリズムと言えます。アルゴリズムの難易度を測るものを複雑度といいます。あるアルゴリズムがどれくらい複雑かというと、多くの場合、解かせたい問題をコンピュータが解くのにどれくらい時間がかかるかを知りたがっているのです。

並び替え

色が書かれたカードを同じ色の山に並べ替えるアルゴリズムの例です。

1. すべてのカードを拾う。
2. 手札からカードを1枚選び、そのカードの色を見てください。
3. その色のカードの山がすでにある場合、このカードをその山の上に置く。
4. その色のカードの山がない場合は、このカードの色だけの山を新たに作る。
5. 手札が残っている場合は、第2ステップに戻ります。
6. 手札が残っていなければ、カードの並べ替えが行われます。あなたは終了です。

番号順に並べる

これらは、多くの異なる数字が書かれたカードの束を、数字が順番になるように並べ替えるアルゴリズムの例です。

プレイヤーは、まだ整理されていないカードの束からスタートします。

第一アルゴリズム

このアルゴリズムは、カードの束を1枚ずつ調べていきます。このカードは、積み重ねられたカードの次のカードと比較される。この位置が変わるのはステップ6だけであることに注意してください。このアルゴリズムはバブルソートと呼ばれます。遅いです。

1. カードの束が空であるか、1枚しか入っていなければ、ソートされたことになり、終了となります。
2. カードの束を取ります。カードの束の最初のカード(一番上)を見てください。
3. あなたが見ているカードはカードAです。カードAが現在ある位置は、スタックPの中です。
4. カードA以降のカードがない場合は、手順8へ。
5. 次のカードは、カードBです。
6. カードBの数字がカードAより小さかったら、カードAとBの位置を入れ替えましょう。カードを入れ替えたとき、位置Pは変えないでください。
7. Pの位置の後に別のカードがある場合は、それを見て、手順3に戻る。
8. 最後の実行でカードの位置を入れ替えなかった場合は、終了となり、カードの山はソートされます。
9. そうでない場合は、手順2に戻ってください。

ステップバイステップの例

5 1 4 2 8」という数字が書かれたカードの束を、このアルゴリズムを使って小さい数字から大きい数字へと並べ替えてみましょう。各ステップでは、太字で書かれた要素を比較する。カードの束の一番上が左側です。

First pass:
( 5 1 4 2 8 ) → { {displaystyle \to } }.( 1 5 4 2 8 ) ここで、アルゴリズムは最初の2つの要素を比較し、それらを交換します。
( 1 5 4 2 8 ) → {displaystyle \to }.( 1 4 5 2 8 )
( 1 4 5 2 8 ) → {displaystyle \to }.( 1 4 2 5 8 )
( 1 4 2 5 8 ) → { {displaystyle \to } }.( 1 4 2 5 8 ) これらの要素はすでに順番が決まっているので、アルゴリズムはそれらを入れ替えることはありません。
2パス目:
( 1 4 2 5 8 ) → {displaystyle \to }.( 1 4 2 5 8 )
( 1 4 2 5 8 ) → {displaystyle \to }.( 1 2 4 5 8 )
( 1 2 4 5 8 ) → { {displaystyle \to } }.( 1 2 4 5 8 )
( 1 2 4 5 8 ) → { {displaystyle \to } }.( 1 2 4 5 8 )
さて、カードの束はすでにソートされていますが、我々のアルゴリズムはこのことを知りません。アルゴリズムは、ソートされていることを知るために、スワップなしで1パス全体が必要です。
3パス目:
( 1 2 4 5 8 ) → {displaystyle \to }.( 1 2 4 5 8 )
( 1 2 4 5 8 ) → { {displaystyle \to } }.( 1 2 4 5 8 )
( 1 2 4 5 8 ) → { {displaystyle \to } }.( 1 2 4 5 8 )
( 1 2 4 5 8 ) → { {displaystyle \to } }.( 1 2 4 5 8 )
最後に、配列はソートされ、アルゴリズムは停止することができます。

沿革

これはソートのアルゴリズムとしてわかりやすいものです。コンピュータ科学者は、小さい要素が実行ごとに位置を変えながら上に上がっていくことから、バブルソートと呼びました。残念ながら、このアルゴリズムは、ソートに長い時間（カードの山を何度も通過する）を必要とするため、あまり良いものではありません。

第2アルゴリズム

このアルゴリズムは、もう一つの考え方を用いています。ある問題を解くのは難しいが、その問題をより解きやすい単純な問題で構成するように変更できる場合がある。これを再帰という。最初の例より理解が難しいが、より良いアルゴリズムが得られるだろう。

基本的な考え方

1. スタックにカードがない、または1枚しかない場合、ソートされて終了です。
2. カードの束をほぼ同じ大きさの半分に分ける。カードの枚数が奇数であれば、2つの積み重ねのうち、どちらかが1枚多くなっているはずです。
3. 2つのスタックのそれぞれを、このアルゴリズムでソートする（各スタックについて、このリストの項目1から始める）。
4. 以下のように、ソートされた2つのスタックをマージする。
5. その結果、カードの束がソートされます。これで完成です。

2つのスタックを合体させる

これは、2枚のカードの束で動作します。そのうちの1つをA、もう1つをBと呼び、3つ目のスタックはCと呼ばれ、始めは空です。

1. スタックAかスタックBのどちらかが空の場合、空でない方のスタックのカードをすべてスタックCの上に置くと、マージが完了し、スタックCがその結果となります。(注意：スタック全部をスタックCの上に置いてください。カードごとに置くと順番が変わってしまい、思うようにいきません)。
2. 積み木Aと積み木Bの一番上のカードを見て、数字の小さい方を積み木Cの上に置く。積み木Cにカードが入っていなかった場合、1枚のカードになる。
3. 積み木Aか積み木Bのどちらかにカードが残っていたら、手順1に戻って仕分けをする。

沿革

ジョン・フォン・ノイマンは1945年にこのアルゴリズムを開発した。彼はこれを数によるソートとは呼ばず、マージソートと呼んだ。このアルゴリズムは、他のアルゴリズムと比較して、非常に優れたソートアルゴリズムです。

第3のアルゴリズム

最初のアルゴリズムは、2番目のアルゴリズムに比べてカードの並べ替えにはるかに時間がかかりますが、改善（改良）することは可能です。バブルソートを見ると、数字の大きいカードはすぐに山の上から移動するが、山の下の数字の小さいカードは上昇（上部に移動）するのに時間がかかることがわかる。最初のアルゴリズムを改良するために、次のようなアイデアがあります。

隣り合った2枚のカードを比較するのではなく、最初に「特別な」カードを選びます。他のカードはすべて、このカードと比較されます。

1. 最初にスタックAがあり、他に後で作成するスタックBとCがあります。
2. 積み荷Aにカードが1枚もないか、1枚しかない場合、仕分けは終了です。
3. 積み荷Aから、可能ならランダムにカードを1枚選ぶ。これをピボットと呼ぶ。
4. 積み荷Aの残りのカードはすべて、このピボットと比較される。小さい数字のカードは積み木Bへ、同じか大きい数字のカードは積み木Cへ。
5. スタックBやスタックCにカードがある場合、これらのスタックを同じアルゴリズムでソートする必要があります（スタックB、スタックCともにこのリストのpos 1から順番にスタートします）。
6. 完了しました。並べ替えられた札束は、まず並べ替えられた札束Bがあり、次にピボットがあり、そして並べ替えられた札束Cがあります。

沿革

1960年にC.A.R.Hoareによって開発されたアルゴリズム。現在、最も広く使われているソートアルゴリズムの一つである。クイックソートと呼ばれる。

バブルソートの仕組みがわかるアニメーション


2番目の数字による並べ替えアルゴリズム（Mergesort）を使って7つの数字を並べ替えること


カードをソートする第3のアルゴリズム。赤いバーがある要素がピボットとして選ばれる。スタート時はすべて右側の要素です。このアルゴリズムはクイックソートと呼ばれます。

アルゴリズムを組み立てる

色と数字が書かれたカードがある場合、「色で並べ替え」アルゴリズムを行い、次に各色の積み重ねに対して「数字で並べ替え」アルゴリズムを行い、積み重ねをまとめると、色と数字で並べ替えることができます。

数字による並べ替えのアルゴリズムは、色による並べ替えのアルゴリズムよりも、何度も手順をやり直さなければならないことがあるので、より難しい。数字による並べ替えはより複雑であると言えるでしょう。

関連ページ

• ユークリッド・アルゴリズムは2000年以上前に発見された。2つの数の最大公約数を求めることができる。