プログラミングの記事一覧

クイックソート

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-5a5e39d80e540485677985/] 実行結果 [crayon-5a5e39d80e54a547467887/] ソート関数の解説 ...

Read More...

バブルソート

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

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

Read More...

「プログラマーって分からない関数に出くわしたら終了なの?」について

Posted on Tuesday, September 2nd, 2014 18:35:57

某掲示板の某IT系スレのまとめサイトで、「プログラマーって分からない関数に出くわしたら終了なの?」というスレを見つけました。質問の内容は、以下の通りです。 例えば Pushbackinput streambufferreader() こういう関数を使えと仕様書に書いてあったとして、何これ?って なってネットでも調べても無いし、先輩に聞いても分らない 場合どうしてんの?仕...

Read More...

一時変数を使わずにスワップ

Posted on Sunday, August 31st, 2014 21:10:36

同じ型の2つの変数の値を交換する際、通常は一時変数を用意して、以下のようなアルゴリズムで行います。 [crayon-5a5e39d80ee8e144434538/] しかし、XOR交換アルゴリズムを用いれば一時変数なしでスワップできます。よく分からない場合はベン図を書いてみると良いでしょう。 [crayon-5a5e39d80ee96911458988/] また、加算と減算を...

Read More...

rspec の実行で “uninitialized constant Capybara (NameError)”

Posted on Thursday, August 28th, 2014 20:49:19

Ruby on Rails チュートリアルの第3章で、下記の rspec コマンドを実行すると、「Capybara がないよ!」ってエラーが発生しました。 ※ チュートリアル通りに進めないのは、恐らくチュートリアルで指定されている各種ソフトウェアのバージョンを全て無視して、全て最新バージョンで行っているためかと思われます。 [crayon-5a5e39d80f3c9453450341/] ...

Read More...

Web プログラマーのスタートダッシュには Ruby on Rails チュートリアル がオススメ

Posted on Tuesday, August 26th, 2014 21:22:57

Ruby on Rails の学び方 なんか Web でグリグリ動くものが書きたいなーということで、Ruby on Rails を始めました。"How to build a blog engine in 15 minutes with Rails"なんてのがありますが、その分学び方次第ではライブラリがないと何もできない開発者になってしまうわけです。 https://www.youtube....

Read More...

OS X Marvericks に Ruby on Rails の環境を構築する手順

Posted on Monday, August 25th, 2014 17:23:43

最近プログラム書いてないので、ちょっと Rails でも始めてみます。せっかくゼロからやるので、環境構築手順を残します。OSは、OS X Marvericksです。 Command Line Tools のインストール Command Line Tools この後インストールする Homebrew を利用するためには、Command Line Tools をインストールする必要が...

Read More...