文系が学ぶコンピューターサイエンス╭( ･ㅂ･)و ̑̑：第６回【単純挿入ソート】
単純挿入ソートとは？
左(あるいは右)端からソート済みの区間がどんどん広がっていくというイメージでとらえる。
ソート済みの値より小さいものがあったら、それを挿入するために、
その値より大きい挿入済みの配列を1個ずつずらすやり方。
// 単純挿入ソート。最悪計算量O(n^2)。ループ回数から考えるとまあわかる。 insersionSort: function(data) { // 最初から最後までソート完了になるまで繰り返す var tmp, i; for (var sorted = 0; sorted < data.length - 1; sorted++) { // ソート完了している領域の直後の値を取り出す。 insert = data[sorted+1]; // ソート済みの中で、挿入できる場所があるかを調べる。 for (i = 0; i <= sorted; i++) { if (data[i] > insert) { break; //ずれている部分を記憶しつつ、サーチを止める。 } } // ずれていた箇所まで、1個ずつ要素をずらしていく。 // 最終的にずれていた部分、１つの要素で比べようとすると止まる。 while(i <= sorted + 1) { tmp = data[i]; data[i] = insert; insert = tmp; i++; } } return data; }
文系が学ぶコンピューターサイエンス╭( ･ㅂ･)و ̑̑：第５回【選択ソート】
選択ソートとは？
選択ソートとは、配列の先頭と、それ以降の最小値を交換するのを、各値に対して施すソート。
原理はそこまで難しくない。
ある値より先に、自分より小さい値があったら、それのうち一番小さいものと交換して、
どんどん先に進んでいくだけ。
普通はバブルソートの次くらいに学ぶっぽい。
選択ソートの実装
// 選択ソート。計算量O(n^2)。 selectionSort: function(data) { var min; for (var i = 0; i < data.length - 1; i++) { // 先頭を最小値とする。 min = i; // 先頭から順に、それより小さい値があった場合そのうち一番小さいものと交換する。 // for (var j = i + 1; j < data.length; j++) { if (data[min] > data[j]) { min = j }; } if (i != min) { this.swap(data, i, min) }; } return data; }
文系が学ぶコンピューターサイエンス╭( ･ㅂ･)و ̑̑：第４回【コームソート】
コームソートとは？
今回は特に書くことがない。。。
コームとは櫛という意味。
バブルソートで少し間隔をとって比較して、徐々に近づけてくソート。
バブルソートと違って、すべての値の交換じゃなく、間隔を調整していくことで回数を減らすという原理。
計算量はO(nLogn)。
コームソートの実装
combSort: function(data) { var N = data.length; var gap = N; while((gap > 1) || flag) { // 収縮率（間隔調整の度合い）は1.3。 var gap = gap*10/13; if (gap < 1) { gap = 1 }; var flag = 0; for (var i = 0; i < N - gap; i++) { if (data[i] > data[i+gap]) { this.swap(data, i, i+gap); flag = 1; } } } return data; }
文系が学ぶコンピューターサイエンス╭( ･ㅂ･)و ̑̑：第３回【マージソート】
マージソートとは？
合体させまくるソート。
ソート済みの配列同士なら、どっちかの配列のちっちゃい方を順にとってけば、
最終的に合成された配列もソートされてるよね、最初に細かく分割して、
それぞれを上記のように合成してこうっていうのがマージソート。
丁寧にいうと、
- 整列済みのリストAとリストBをマージして整列されたリストCを作る。
- リストAとリストBの先頭の要素を比較して、小さい方をリストから削除してリストCの末尾に追加する
- リストA、リストB、どちらか一方の要素がなくなるまで 1. を繰り返す
- 残った要素をリストCの末尾に順に追加する
って感じ。
分割統治法
こういう"細かく分断して、それぞれの単位で問題を解決して、最終的にでかい問題を解決しよう"って手法を、分割統治法というらしい。
マージソートはその代表例。
破壊と創造。再構築。
マージソートのコード
以下実装。ちなみに計算量はNlogNらしいよ。
マージソートの論理的構造であるツリーの深さは、データの数を n とすれば logn となり、各階層で n 回の比較演算がなされるから。
// MergeSort mergeSort: function(items){ var self = this; // 受け取ったdata(配列)が、最小単位になるまで分割し続ける。 if (items.length < 2) { return items; } var middle = Math.floor(items.length / 2), left = items.slice(0, middle), right = items.slice(middle); return this.merge(self.mergeSort(left), self.mergeSort(right)); }, merge: function(left, right){ var result = [], il = 0, ir = 0; while (il < left.length && ir < right.length){ if (left[il] < right[ir]){ result.push(left[il++]); } else { result.push(right[ir++]); } } // 配列で余った一番大きい値を最後にresultに入れて終了。 return result.concat(left.slice(il)).concat(right.slice(ir)); }
bower installでlogでるのにbower_componentsが作成されないバグ
## 概要
bower installすると、.bowerrcやbower.jsonの設定もbower自体も特に問題ないのにbower_componentsが作成されませんでした。
bower installも
bower angular#>=1.2.* not-cached git://github.com/angular/bower-angular.git#>=1.2.* bower angular#>=1.2.* resolve git://github.com/angular/bower-angular.git#>=1.2.* bower json3#~3.3.1 not-cached git://github.com/bestiejs/json3.git#~3.3.1 bower json3#~3.3.1 resolve git://github.com/bestiejs/json3.git#~3.3.1 bower es5-shim#~3.0.1 not-cached git://github.com/es-shims/es5-shim.git#~3.0.1 bower es5-shim#~3.0.1 resolve git://github.com/es-shims/es5-shim.git#~3.0.1 bower jquery#~1.11.0 not-cached git://github.com/jquery/jquery.git#~1.11.0 bower jquery#~1.11.0 resolve git://github.com/jquery/jquery.git#~1.11.0 bower bootstrap#~3.1.1 not-cached git://github.com/twbs/bootstrap.git#~3.1.1 bower bootstrap#~3.1.1 resolve git://github.com/twbs/bootstrap.git#~3.1.1 bower angular-resource#>=1.2.* not-cached git://github.com/angular/bower-angular-resource.git#>=1.2.* bower angular-resource#>=1.2.* resolve git://github.com/angular/bower-angular-resource.git#>=1.2.* bower bootstrap-sass-official#~3.1.1 not-cached git://github.com/twbs/bootstrap-sass.git#~3.1.1 bower bootstrap-sass-official#~3.1.1 resolve git://github.com/twbs/bootstrap-sass.git#~3.1.1 bower angular-cookies#>=1.2.* not-cached git://github.com/angular/bower-angular-cookies.git#>=1.2.* bower angular-cookies#>=1.2.* resolve git://github.com/angular/bower-angular-cookies.git#>=1.2.* bower angular-sanitize#>=1.2.* not-cached git://github.com/angular/bower-angular-sanitize.git#>=1.2.* bower angular-sanitize#>=1.2.* resolve git://github.com/angular/bower-angular-sanitize.git#>=1.2.* bower angular-bootstrap#~0.11.0 not-cached git://github.com/angular-ui/bootstrap-bower.git#~0.11.0 bower angular-bootstrap#~0.11.0 resolve git://github.com/angular-ui/bootstrap-bower.git#~0.11.0
みたいに表示されるけれど、logだけで結局git checkoutできてない。
ローカルではできたのに。
## 原因
nodeのバージョンがローカルと異なっていた。
nodeのバージョンが0.10.0以上でないといけないのだが、0.8.5だったためbowerがうまく動いていなかった。
$ sudo npm cache clean -f $ sudo npm install -g n $ sudo n stable $ node -v
で治る。
文系が学ぶコンピューターサイエンス：第２回【計算量、クイックソート】
「クイックソート」とは？
早いソート。後述ですが最初何やってるのかわかりませんでした。
アルゴリズムが可視化されている動画見てもさっぱりわかりません。
ゲーマーなのでクイックマンを思い出さずにはいられない。
※アルゴリズム可視化はここから
http://visualgo.net
クイックソートは、以下のような手順でソートします。
- ソートを分割するために基準値を決める
- 左から順に、基準値より大きな値を探す
- 右から順に、基準値より小さな値を探す
- 交換する
- 基準値の左は小さい値、右は大きい値になったら、終了
- これが完全に終了するまで再帰
です。基準値より大小の値を探すときは、配列で1個ずつ基準値に近づいていって、もし調べる対象がすれ違ったら（基準値の周りが全部大小関係が整理されたら）、そのサイクルは終了です。
今回のコードでは、基準値を左端の値で置いてます。
これは真ん中を基準値にとったりするケースもありますが、
乱数の配列ならどっちが明確に早いとかはとくにないっぽいです。
※参考
Algorithms with Python / 整列 (ソート)
クイックソート
Computer science in JavaScript: Quicksort | NCZOnline
「時間計算量」とは？
バブルソートのところで触れ忘れたんですが、アルゴリズムを勉強するときは必ず時間計算量ってやつを知っておいたおいたほうがいいっぽいですね。
時間計算量というのは、「コードへのデータ入力量が多くなった時、どれくらい、どのように処理時間が増加するかを表した式」です。
時間計算量はオーダー記法というやつで書き表されます。
その値は、だいたいループの回数に依存します。
例えば前回やったバブルソートは、最悪の場合すなわち一番時間がかかる場合は全部逆順に並んでいる時ですね。
1 2 3 4 5 6 が正解なら、 6 5 4 3 2 1 のときが最悪。 一個一個前に持ってこなきゃいけない。
このとき、1を左端に持ってくるまでに５回（6-1、抽象化するとn-1回）かかります。
この流れを繰り返すと、2を1の次に持ってくるまで5-1=4回(抽象化するとn-2回)ですし、
これらを合計すると、(n-1)+(n-2)+...+1 = Σn = n(n-1)/2回です。
（これはただの数列の話なのでなんとか文系の僕でもわかります）
で、時間計算量は係数省いて、1とか2とかの誤差の範囲は削って収束させちゃうので、
この場合だと1/2を1にして、n(n-1)のn-1をnにまとめちゃって、結果n^2になります。
ここでオーダー記法ってやつを使って、O(n^2)と表すのが、時間計算量の掟らしいです。
以上、計算量の性質をまとめると、
- 計算量は、アルゴリズムを評価する為に使用する
- 計算量は、大体の場合はループの回数と一致する
- 計算量は、最大指数項のみを残し係数は省く
です。
クイックソートはなぜ早い？
クイックソートの話に戻ります。
名前はシンプルなんですが、こいつくっそ理解できないです。
なんでかっていうと、クイックな理由がいまいちわからんからです。
まあ再帰的に処理を分割していくからでしょう。
計算量はこちらを参考にしました。
計算式超丁寧です。ありがとうございます。文系の僕でもわかった。
バブルソートのO(n^2)よりO(nlogn)が小さそうなのはなんとなくわかります。
クイックソートのコード
以下の通りです。前回からのソースの差分はこちら
quicksort · 980d1b4 · timakin/jsalgo · GitHub
function Sort() {} Sort.prototype = { swap: function(items, lower, upper) { var temp = items[lower]; items[lower] = items[upper]; items[upper] = temp; }, // クイックソートの基準値を返す関数 partition: function (data, bottom, top) { var pivot = data[bottom]; // 両端の値を設定。 var lower = bottom; var upper = top; while (lower <= upper) { while (data[lower] < pivot) { lower++; } while (data[upper] > pivot) { upper--; } if (lower <= upper) { this.swap(data, lower, upper); lower++; upper--; } } return lower; }, quick: function (data, bottom, top) { var self = this; if (bottom >= top) { return; } // 基準値の周りで並び替えが終わったらそのサイクルは終了。 // ここからがいわゆるpartition（基準点）を作る処理 // 便宜上左端の値を基準値にしている。 var index = self.partition(data, bottom, top); self.quick(data, bottom, index-1); self.quick(data, index, top); return data; } }
文系が学ぶコンピューターサイエンス：第１回【概要、バブルソート実装】
なぜコンピューターサイエンスを学ぶのか
最近コンピューターサイエンスを学ばなきゃいけない空気を感じます。
特にデータ構造とアルゴリズム、ビット操作とか。
背景としては以下のような理由が。
- 給与高いとか産業自体面白そうとか思われるし、初学のハードルは低くなっている分初心者エンジニアは増える。
- スマートニュースさんとかそうですけど、ガチエンジニアならデータ構造とアルゴリズムできて当然だろ？転職できると思ってんの？みたいな採用基準がある。
- 実務を通じて設計でもう２度と苦労したくないと思った。まじ効率大事。
だから、基礎のデータ構造とアルゴリズムくらいちゃんとできてないと生存戦略がままならないです。
周囲の情報学部出身にそんな理由でボコボコにされるのは哀しい。
ぼこぼこにしてくる情報学科出身とぼく
前提として、僕はおよそ３年くらいインターンとしてエンジニアをしてます。
gemとかも作ってるし、自分でプロダクトも作りました。
timakin (timakin) · GitHub
また、数学に関しては好きでも嫌いでもないくらいなので、理論は詳しくないです。
ただ、以上のような状況で迫られて今回データ構造とアルゴリズムくらいは学ぶことにしました。
今まで一応何度もトライしたんですが、やっぱ自分で書かないと、身につかないです。
JavaScriptで実装
この企画ではアルゴリズムをJavaScriptで実装します。
あんま好きじゃないですが、サイドプロジェクトのアプリがMEAN Stackなので、
どうしてもJavaScriptに慣れる必要があり、今回選択しました。
あとブラウザで確認しやすいのでうれしい。MEANはこちら。
MEAN.IO - MongoDB, Express, Angularjs Node.js powered fullstack web framework
参考資料
SoftBank Creative出版のアルゴリズムとデータ構造第２版を使います。
- 作者: 紀平拓男,春日伸弥
- 出版社/メーカー: ソフトバンククリエイティブ
- 発売日: 2011/03/30
- メディア: 単行本
- 購入: 15人 クリック: 255回
- この商品を含むブログ (31件) を見る
元のコードは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()));
