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