読書
ハッシュと挿入ソートを組み合わせたソートである。 ハッシュ関数により、要素をいくつかの小さいバケツに分ける。 そして、それぞれのバケツの中で挿入ソートを行う。 挿入ソートはO(n^2)なので、それぞれのバケツ中の要素数が少ないほど高速。したがって、…
別名「数え上げソート」と呼ばれ、その名のとおりそれぞれの要素がいくつあるかを数えていく。 数え上げた結果の累積分布表と原配列を参照し、要素の挿入を行うことでソートが完了する。 そのため、数値を比較する必要がなく高速にソートを行える。今回は累…
10/28-11/4 スタック キュー リスト 解説(11/4 14:00-16:00) 11/5-11/10 二分木 解説(11/10 14:00-16:00) 11/11-11/17 セット 解説(11/17 14:00-16:00) 11/18-11/24 ソート 解説(11/24 14:00-16:00) 11/25-11/30 探索 解説(11/30 14:00-16:00) 12/1-12/14 グ…
ソート済みの２つの配列をマージ（結合）することでソートを行う。 配列を２つに分割するため、分割統治法を用いているソートとなる。 計算量はO(nlogn)であり、傾向はヒープソートと同じである。 しかし、配列の左部分をバッファに退避するため、要素数に比…
中央値ソートをベースに処理を簡単にしたソート。 平均計算量はO(nlogn)であるが、最悪時はO(n^2)となる。 アルゴリズムとしては分割統治法に分類される。今回は高速化のため、以下の点に取り組んだ。 ・再帰処理を省くためループで実装 ・3つの値から中央値…
単純挿入ソートの発展版。 整列されていればされているほど高速になるため、 部分的に単純挿入ソートを繰り返すことで性能を向上させる。クイックソート登場前は最速のソートだったらしい。 #rubyでループをうまく書けず簡潔でないコードになっている #挿入…
2番目の要素から先頭に向かって適当な位置に挿入をしていく。 計算量はO(n^2)。 最良時はそれぞれの要素が適当な位置に収まっていることを確認するためのO(n)。 ソート済みの部分が多いときは高速だが、要素を１つずらすコストが高い。 したがって、ランダム…
最小の値を選択して、先頭から順番に交換していく。 計算量はO(n^2)。離れた要素の交換が発生する可能性があるため 安定ではない def selectionsort!(array) 0.step(array.size - 1, 1) do |head| indexOfMin = array.size - 1 (array.size - 1).step(head, …
となりの要素が大きければ、となりの要素と交換を繰り返す。 計算量はO(n^2)。 安定的なアルゴリズム。 #最後に入れ替えが発生した場所を記憶しておくことで、 #それより前の場所では入れ替えの必要がないことが分かる。 #今回は実装していない。 def bubble…
安定的 同一キー値を持つデータの位置関係がソート前後においても保たれるアルゴリズムを安定的なソートと呼ぶ。 たとえば、テストの点数をキー値とし学籍番号と一緒に保存している場合、 「学籍番号:1 点数:70」と「学籍番号:2 点数:70」の順番がソート後も…
ポインタではなく配列を利用した単方向リスト。 空き領域の管理が面白かった。
ポインタを利用した単方向リスト。 容易に可変長のリストが作れるかわり、メモリ消費量が増えます。 操作を限定すればキューとしても、リストとしても使用できます。 発展版として、双方向リストや循環リスト、二分木が存在します。
First In First Outのデータ構造です。 リングバッファ版は空き領域を埋めるためにずらす処理が不要となるため、通常の配列を使用した実装より高速です。
Last In First Outのデータ構造。 データを取り出すと最後に追加したデータが取り出されます。
10/28-11/4 スタック キュー リスト 解説(11/4 14:00-16:00) 11/5-11/10 二分木 解説(11/10 14:00-16:00) 11/11-11/17 セット 解説(11/17 14:00-16:00) 11/18-11/24 ソート 解説(11/24 14:00-16:00) 11/25-11/30 探索 解説(11/30 14:00-16:00) 12/1-12/14 グ…
7/19(金)にOracle認定 Javaプログラマ SE6を受験します。 この週末に黒本問題集の模擬問題を1回。 その後は、型変換、スレッド、コレクションの問題をやって理解を深めます。 Java How to Program 並行して、Java How To Programも読み進めていきます。 inte…
学習内容 Aizu Online Judge 0019 Factorial 0020 Capitalize 0021 Parallelism Code Compelete 第2版 下 Chapter26 コードチューニングテクニック 試行錯誤ではいけない こうやったらうまくいくのではないだろうか、というコードの修正が多いと感じる。 そ…
学習内容 Aizu Online Judge 0000 QQ 0001 List of Top 3 Hills 0002 Digit Number 0003 Is it a Right Triangle? Code Complete 第2版 上 第16章 ループの制御 for文の利点 ループの先頭で一度セットアップしたら、後は忘れてしまえる。 ループの先頭にコー…
学習内容 Aichi Online Judgement 10018 Toggling Cases 10019 Sum of Numbers 10020 Counting Characters プログラマが知るべき97のこと 28.魔法に頼りすぎてはいけない キャスト eclipseなので型変換ができなければ警告してくれるが、コードを打ち込む前に…
学習内容 メモ帳 ダイアログのモーダルダイアログ化 Aichi Online Judgement 10003 Small, Large, or Equal 10004 Sorting Three Numbers 10005 Print Many Hello World 10006 Print Test Cases 10007 Swapping Two Numbers 10008 A / B Problems 10009 Circ…
学習内容 CodeComplete 第2版 上 14章 ストレートなコードの構成 15章 条件文の使用 19章 制御構造の問題 プログラマが知るべき97のこと 97.ステートに注目する 82.他者への思いやりを意識したコーディング 実行順序の依存性を明白に ルーチン名、引数、コメ…
学習内容 Aichi Online Judgement 10001 X Cubic(入力された値の３乗を出力する) 10002 Rectangle(入力された２つの値から面積と周りの長さを出力する) プログラマが知るべき97のこと 12.コードは設計である 15.コードの論理的検証 25.見られて恥ずかしいデ…
学習内容 メモ帳作成（ひとまず完成） ディレクトリとファイル名を指定したファイルの読み書き 描画するフォントの変更機能 テキストエリアをスクロール可能に プログラマが知るべき97のこと 46.すべきことは常に明確に fileDialog fileDialogはファイル名（…
学習内容 メモ帳作成 検索機能（検索中にテキストを編集しても反映されない仕様） 置換機能（検索中にテキストを編集しても反映されない仕様） プログラマが知るべき97のこと 84.正しいアルゴリズムとデータ構造を選ぶ １つの変数に２つの意味を持たせない i…
