timakin.log

╭( ・ㅂ・)و ̑̑

文系が学ぶコンピューターサイエンス:第1回【概要、バブルソート実装】

なぜコンピューターサイエンスを学ぶのか

最近コンピューターサイエンスを学ばなきゃいけない空気を感じます。
特にデータ構造とアルゴリズム、ビット操作とか。
背景としては以下のような理由が。

  • 給与高いとか産業自体面白そうとか思われるし、初学のハードルは低くなっている分初心者エンジニアは増える。
  • スマートニュースさんとかそうですけど、ガチエンジニアならデータ構造とアルゴリズムできて当然だろ?転職できると思ってんの?みたいな採用基準がある。
  • 実務を通じて設計でもう2度と苦労したくないと思った。まじ効率大事。

だから、基礎のデータ構造とアルゴリズムくらいちゃんとできてないと生存戦略がままならないです。
周囲の情報学部出身にそんな理由でボコボコにされるのは哀しい。

f:id:u_tis:20150120160949j:plain
ぼこぼこにしてくる情報学科出身とぼく

前提として、僕はおよそ3年くらいインターンとしてエンジニアをしてます。
gemとかも作ってるし、自分でプロダクトも作りました。

timakin (timakin) · GitHub

また、数学に関しては好きでも嫌いでもないくらいなので、理論は詳しくないです。
ただ、以上のような状況で迫られて今回データ構造とアルゴリズムくらいは学ぶことにしました。
今まで一応何度もトライしたんですが、やっぱ自分で書かないと、身につかないです。


JavaScriptで実装

この企画ではアルゴリズムJavaScriptで実装します。
あんま好きじゃないですが、サイドプロジェクトのアプリがMEAN Stackなので、
どうしてもJavaScriptに慣れる必要があり、今回選択しました。
あとブラウザで確認しやすいのでうれしい。MEANはこちら。


MEAN.IO - MongoDB, Express, Angularjs Node.js powered fullstack web framework

参考資料

SoftBank Creative出版のアルゴリズムとデータ構造第2版を使います。

プログラミングの宝箱 アルゴリズムとデータ構造 第2版

プログラミングの宝箱 アルゴリズムとデータ構造 第2版

元のコードはCなんですけど、実務で使う方がいいです。
Rubyとかも考えたんですが、もう最近はWeb界隈でJavaScript以外だと周囲に嘲りの目で見られるので、やめました。これも哀しい。

早速実装バブルソート

早速バブルソート実装しました。
バブルソートというのは、「先頭から順に見て行って、並びがおかしいならそこを入れ替える。おかしいとこなくなるまで最初から繰り返し。」っていう単純なやつです。
実装するにあたって必要になる処理は、

  • 全部の値に対してループをかける
  • 前後で比較して、スワップ(単純な入れ替え)をする
  • スワップするたびにフラグをたてて、ループの最後でフラグが立ってたら、入れ替えがなく順序通りなので、ソート成功。ループから脱する。

です。

コード

今回実装に当たってコードはGithubにあげました。
index.htmlを見るとコンソールで結果を確認できます。

timakin/jsalgo · GitHub

以下実装。

<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <title>JSALGO</title>
  <script src="./lib/sort.js"></script>
</head>
<body>
</body>
</html>
var sortTarget = function () {
  var array = new Array();
  for (var i = 0; i < 100; i++) {
    array.push(Math.random()*1000);
  };
  return array;
}

function Sort() {}
Sort.prototype = {
  bubble: function (sort) {
    do {
      var flag = 0;
      for (var i = 0; i < sort.length; i++) {
        if (sort[i] > sort[i+1]) {
          flag = 1
          j = sort[i];
          sort[i] = sort[i+1];
          sort[i+1] = j;
        }
      };
    }while(flag);
    return sort;
  }
}

var sort = new Sort();
console.log(sort.bubble(sortTarget()));