アルゴリズムの記事一覧

ユークリッドの互除法

Posted on Monday, September 8th, 2014 18:06:03

プログラミング100日チャレンジということで、ソートアルゴリズムをいくつか組んできました。クイックソートで再起アルゴリズムが出てきましたが、今日はもっと簡単で代表的なアルゴリズムをやります。小学生でも知っている人は知っている、ユークリッドの互除法です。明示的に記述された最古のアルゴリズムなんて言われています。 ユークリッドの互除法とは 最大公約数(Greatest Common Divis...

Read More...

クイックソート

Posted on Sunday, September 7th, 2014 20:38:34

クイックソートとは 今回は"言うは易し、書くは難し"なアルゴリズムです。クイックソートは、ある要素を軸に分割を繰り返しながら整列を行うアルゴリズムで、分割統治法と一種です。 データの要素数を n とすると、平均計算量が O(n log n) で、ランダムなデータに対して最も高速なソートアルゴリズムであるとされています。開発者のアントニー・ホーアは、あまりの早さに"quick"のワードを付け...

Read More...

挿入ソート

Posted on Saturday, September 6th, 2014 17:27:31

挿入ソートとは 今回は人間にとって大変分かりやすいアルゴリズムです。まず、配列の最初の2つを取り出してソートします。次に、3つ目の値をソート済みした2つの値と順番に比較して、適切な位置に挿入します。以降も同様にソート済みの配列の適切な位置に新しい値を挿入していくだけです。 とかいう説明をするとややこしいですが、トランプの大富豪なんかをやる時に、配られた手札を並び替えますよね。多くの人は挿入...

Read More...

選択ソート

Posted on Friday, September 5th, 2014 11:47:48

選択ソートとは 前回のバブルソートに続いて単純なソートアルゴリズムです。配列された要素から、最大値/最小値を探索し、ソートされていない最後の要素とスワップするだけです。 サンプル ソースプログラム [crayon-5a3293aa760e6029248039/] 実行結果 [crayon-5a3293aa760f1297543264/] ソート関数の解説 ...

Read More...

バブルソート

Posted on Thursday, September 4th, 2014 17:15:35

100日チャレンジとして、毎日小さなプログラムを組むことにしました。まずは、ソートアルゴリズムを C で組んでみようと思います。今日はバブルソートです。 バブルソートとは バブルソートのアルゴリズムは単純で、全ての要素を舐めていって、隣接する要素と比較して順序が逆であればスワップすることを、(要素数 - 1)回繰り返すだけの安定なソートです。そのため、最悪計算時間が O(n2) になります...

Read More...