Java でアルゴリズムの復習。久しぶりに書くとすっかり忘れてますね...。こういうのを呼吸するように書けるようになりたいものです。
バブルソート
配列の先頭から隣り合う要素を比較して入れ替える。これを配列の最後の要素まで繰り返してソートする。
クイックソート
ここでは配列の真ん中の要素をピボットとする。ピボットの左右で要素を比較し、ピボットより小さい要素が左に、ピボットより大きい要素が右に来るように入れ替える。ピボット未満の要素の配列とピボット以上の要素の配列で同様のソートを再帰的に繰り返してソートする。ピボットを境界にして再帰するには入れ替え処理で使ったインデックスをそのまま返す。最初のピボットの位置ではない。(入れ替えでピボットの位置が変わるため)
マージソート
配列を単一要素になるまで分割する。ソートする要素を作業配列に入れておいて、比較しながら元の配列に書き戻すことでソートする。
二分探索
ソート済みの配列を前提とする。真ん中の要素と対象の要素を比較して左か右の配列を再帰的に探索する。
(番外編) フィボナッチ数
これはアルゴリズムではないかもしれないが、みんなが大好きなフィボナッチ数。通常バージョンとメモ化バージョン。
(番外編) 素数判定
これもアルゴリズムではないかもしれないが、みんなが大好きな素数。判定は平方根以下の値までとする。(対象の値が合成数の場合、平方根より小さい素因数が存在するため)
