バブルソートの特徴は安定なソートであること。
安定なソートとは、ソートのキーが同じ場合、なんどやっても同じ順番になるということ。
ただし、隣同士を比較する演算「A[j] < A[j - 1]」を「A[j] <= A[j - 1]」とすると、キーが同じ場合に
比較演算をしてしまうため、安定でなくなるので注意。

計算量は、最悪の場合はすべて逆順のときで、挿入ソートと同じくデータ数Nの時
(N-1) + (N-2) + …+ 2 + 1 = N(N-1)/2
となる。

■ソースコードgithub.com

■参考資料

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

作者: 渡部有隆,Ozy(協力),秋葉拓哉(協力)
出版社/メーカー: マイナビ
発売日: 2015/01/30
メディア: 単行本（ソフトカバー）
この商品を含むブログ (4件) を見る

2015-09-21

GitHubの使い方

準備

練習の記録を残すために、GitHubでのコード保存をすることにした。

参考にしたのは、以下のページ。

手順どおりに実施したところすぐにできた。

参考URL

[GitHubの使い方：画像付き] GitHubデビューが意外と簡単だった！！tontotakumi.com

2015-09-21

初等ソート

初等ソートアルゴリズム

ソートは計算量の見積もり練習として良い題材となる。
(for文から直感的に見積もることができるから。)
for文はプログラム中でも頻繁に使うため、実践的である。

初等とは、効率が悪い事もあるが、実装が簡単という意味である。

以下にアルゴリズムを紹介する。

１、挿入ソート
トランプを床に並べてソートするときに行うとイメージしやす
い。
まず、引いたトランプ(対象)と床に並べたトランプを比較する。
トランプが収まる位置を作るように、挿入する位置から右(左)のすべてのカードを一枚分ずらし、
対象のトランプを挿入する。
これを繰り返す。

計算量について、最初から昇順(降順)にならんでいる場合は、トランプでいうと床に並べていくだけなので、
トランプN枚に対してN回で済む。

一方、最悪の場合は逆順にならんでいた場合で、各iのループでi回(jのループ回数)ループが発生するので、
1 + 2 + 3 + … + (N-2) + (N-1) = N(N-1)/2
となる。
(高校でやる等差数列の公式「初項 a，公差 d，項数 n，末項lの等差数列の初項から第 n 項までの和 Sn はSn=n(a + l) /2」より)

このため、挿入ソートはデータの初期の並び順で計算回数が大きく影響を受ける。

コーディングとしては、「A[j + 1] = v」が引っかかった。
これは、条件でブレークした際、j--されるため、j+1が挿入位置となる。

■ソース
https://github.com/JunKojima/algorithm/blob/master/3-2_insertsort.c

■参考書籍

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

作者: 渡部有隆,Ozy(協力),秋葉拓哉(協力)
出版社/メーカー: マイナビ
発売日: 2015/01/30
メディア: 単行本（ソフトカバー）
この商品を含むブログ (4件) を見る

2015-06-06

MySQLにCSVデータをロード

大量のデータをMySQLに入れる時、CSVを利用することがある。

mysql> select * from students;
+------+------+
| name | age  |
+------+------+
| Shin |   45 |
+------+------+
1 row in set (0.03 sec)

この状態から、CSVファイルをロードしてみる。

LOAD DATA INFILE '/Users/homedir/data/t.csv' INTO TABLE students FIELDS TERMINATED BY ',';
Query OK, 2 rows affected (0.01 sec)
Records: 2  Deleted: 0  Skipped: 0  Warnings: 0

ロード後のテーブル。

mysql> select * from students;
+-----------+------+
| name      | age  |
+-----------+------+
| Shin      |   45 |
| Hiroshi |   42 |
| Masaru  |   15 |
+-----------+------+
3 rows in set (0.00 sec)

無事追加されている。

2015-01-18

初めてのRuby~1章~読了

１章読了しました。
プログラムの細かい話はまだ出てきませんが、俯瞰的にRubyのことが書いてあります。

・バージョン体系
　MAJOR.MINOR.TEENY(1.4.2)で表記される。
　MINORは偶数が安定版、奇数が開発版
　1.9では上記法則ではないので注意(2.0に備えたらしい)

・ライブラリの探し方
　①専用文法はあるか
　②組み込み関数はあるか
　③組み込みクラスはあるか
　④標準添付ライブラリはあるか
　⑤標準外ライブラリはあるか

Bashでは組み込みか外部かで実行速度に大きな違いがあったが、Rubyでは実行速度にどれだけ差があるのか、慣れてきたら計測してみたい。

・コマンド
　irb :対話型。ちょっとしたコマンドの確認に便利。
　-rdebug :デバッガ制御。行ごとの実行などが行える。
　ri :英語のリファレンスが表示される。

・メソッドの表記方法
　「Stringオブジェクトのインスタンスメソッドeach_byte」= String#each_byte
　「Timeクラスのクラスメソッド*now」= Time.now or Time::now
「::」ってなんだろうと思っていたら、こういう日本語の意味らしい。

・pメソッド
　デバッグ用の出力。
　デバッグ以外での使用は「お行儀が悪い」。

・特異メソッド
　特定のオブジェクトに属するメソッド。

a,b = "str", "str"
def a.greet
  puts "I am the object #{self.object_id}"
end
a.greet  #このオブジェクトだけ使える
b.greet  #エラーになる

ところで、本文に

大部分の演算子はメソッドのシンタックスエラーです。

と書いてあるがなんのことだろう？
シンタックスシュガー = "同じ意味を持つけど別の書き方ができる構文のこと"
らしい。*1

つまりこんな感じの理解。

1.+ 1  #加算メソッドの引数「1」
1 + 1  #加算メソッドのシンタックスシュガー

確かに、シンタックスシュガーの方がわかりやすい。

*1:ぽこつん研究所 » シンタックスシュガー(糖衣構文)について思うこと

計算機の学習メモ

この想像しがたい状況が成立する過程を、以下に詳述する。

安定的なソート

選択ソート

バブルソート

GitHubの使い方

初等ソート

MySQLにCSVデータをロード

初めてのRuby~1章~読了