自由気ままに使える時間は実質あと２日なので、この休みに予定通り解説を行います。 ただ、しっかりとした理解ではないので、「グラフ問題にとりあえず手を付けられるようになる」ことを目標にしたいと思います。

ハッシュと挿入ソートを組み合わせたソートである。 ハッシュ関数により、要素をいくつかの小さいバケツに分ける。 そして、それぞれのバケツの中で挿入ソートを行う。 挿入ソートはO(n^2)なので、それぞれのバケツ中の要素数が少ないほど高速。したがって、…

別名「数え上げソート」と呼ばれ、その名のとおりそれぞれの要素がいくつあるかを数えていく。 数え上げた結果の累積分布表と原配列を参照し、要素の挿入を行うことでソートが完了する。 そのため、数値を比較する必要がなく高速にソートを行える。今回は累…

ソート済みの２つの配列をマージ（結合）することでソートを行う。 配列を２つに分割するため、分割統治法を用いているソートとなる。 計算量は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」の順番がソート後も…