ハッシュと挿入ソートを組み合わせたソートである。 ハッシュ関数により、要素をいくつかの小さいバケツに分ける。 そして、それぞれのバケツの中で挿入ソートを行う。 挿入ソートは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 グ…

そんなに多くのことはできないので、 ソートアルゴリズム アルゴリズムクイックリファレンス 第4章 フローチャートの学習 は終わらせる。 これをなんとかしないと相当遅れが出る。年末年始は Androidプログラミング CodeComplete斜め読み クイックリファレン…

ソート済みの２つの配列をマージ（結合）することでソートを行う。 配列を２つに分割するため、分割統治法を用いているソートとなる。 計算量はO(nlogn)であり、傾向はヒープソートと同じである。 しかし、配列の左部分をバッファに退避するため、要素数に比…

Comptia Network+ 結果： 827/900 ネットワークスぺシャリスト落ちてるだろうから、ためしに受けてみようかと思い受験。 物理層の話が多目なので勉強になった。特にケーブル。次に各種ツール（ケーブル認証テスタとか）。 単語知っているかどうかという内容…

中央値ソートをベースに処理を簡単にしたソート。 平均計算量は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」の順番がソート後も…

コードにバグが存在していました。 後日、修正したプログラムで再測定を行います。 申し訳ございませんでした。以下の記述は多くが誤りとなりますので、ご理解のうえご覧ください。 まことに勝手ながら、諸事情により二分木についての解説を11/29に変更させ…

ポインタではなく配列を利用した単方向リスト。 空き領域の管理が面白かった。

ポインタを利用した単方向リスト。 容易に可変長のリストが作れるかわり、メモリ消費量が増えます。 操作を限定すればキューとしても、リストとしても使用できます。 発展版として、双方向リストや循環リスト、二分木が存在します。

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 グ…

メソッド メソッド 処理 Object#methods メソッド一覧出力 Comparable#between? 引数で与えられた値の間にあるか判定 Numeric#coerce 型を変換して配列にして返す Numeric#eql? 型が等しく、かつ、値が等しいか判定 Numeric#nonzero? 自身がゼロのときnil,そ…

Rubyで簡単なCGIを作った際にしょっぱいミスが多かったので、メモを残しておく。 数値と文字列を連結する際には、数値をto_sで文字列に変換する 行末のセミコロンは不要 入力末尾の改行コードはchompで捨てる ループのための構文は loop do N.times N.times …

感想 Oracle認定 Javaプログラマ SE6に合格しました。正答率は85%でした。 1年以上Javaをやってきた結果が形として出たのかなと前向きにとらえています。試験の難易度は黒本の問題と同じくらいだと感じました。 問題はランダムに選択されるため、運が良かっ…

7/19(金)にOracle認定 Javaプログラマ SE6を受験します。 この週末に黒本問題集の模擬問題を1回。 その後は、型変換、スレッド、コレクションの問題をやって理解を深めます。 Java How to Program 並行して、Java How To Programも読み進めていきます。 inte…

色々ありまして予定していた受験日での受験をとりやめました。 今月一杯でチケットが切れるので、今月中には受験したい。ちなみに、先週はじめてやった模擬試験は31/60でした。 うち15問は理解の浅い項目についての間違いとなっており、より理解を深める必要…

情報セキュリティスペシャリスト試験に合格しました。 午前2 84点 午後1 71点 午後2 76点 でした。午後は自己採点よりも10点前後高い点数で、まわりの友人も同じ状況でした。 合格率は13.1%とのことで、もともとの点数では合格率が低すぎたため、 補正が強く…

oracle認定 javaプログラマの学習を継続しています。 受験日はまだ確定していませんが、６月末の予定です。肝心の学習内容ですが、黒本教科書を１周して章末問題を２周。 その後はsoftbankの問題集で理解を深めています。 基本的には言語仕様の話で一部APIの…

昨年は”忙しい”ことを言い訳に、勉強に使える時間を余暇、睡眠のために使っていました。 その結果か、情報セキュリティスペシャリストは不合格。 Javaまわりの学習（デザインパターン、Android、サーブレット）はほとんど進まず。 もっとレベルアップできた…

http://judge.u-aizu.ac.jp/onlinejudge/rating_note.jspによると、 64 / MIN(512, 正解ユーザー数) という公式によってレーティングが算出されているとのこと。 機械的にコードを評価するのが難しいのか、簡単なレーティング公式となっています。正解ユーザ…

JigsawPuzzleの非受理コード。 枝狩りが十分でないため20秒以内に処理が終了しない。

今後再帰を書くためのメモ。 再帰は大きな部分を小さな部分に分解しやすい場合に役立つ 問題の範囲が広くなると複雑になる 再帰は複雑さを克服することを可能にする 迷路の経路探索 無限再帰を避ける 再帰を終了するための手段を用意する スタックに注意 ス…

昨年は”忙しい”ことを言い訳に、勉強に使える時間を余暇、睡眠のために使っていました。 その結果か、情報セキュリティスペシャリストは不合格。 Javaまわりの学習（デザインパターン、Android、サーブレット）はほとんど進まず。 もっとレベルアップできた…