quick sort
Quick Sort
quick sortは、最悪計算量がO(N2)と知られていますが、乱択アルゴリズムにすることで計算量の期待値がO(N*lgN)になります。
乱択クイックソートの実装は、私がネットで見たものだけで、二つの方法がありました。
- 枢軸（ピボット）をランダムに選ぶ
- 与えられた数列をシャッフルしたあとに、ピボットを選択する
計算量の観点から、前者のほうが適当だと考えたので、前者で実装しました。本実装では、シンプルなクイックソートにアレンジを施しています。ピボットと同値の数は無視することにして、擬似的な3way partition方式にしています*1。
雑記
ケント・ベック『実装パターン』を読みたかったけど、絶版になっていて買えない。大学図書館にも無かった。今度国会図書館に行って読もう。
友人から「大きめの規模を持つシステム（ゲーム）を作っている」という話を聞いて興味がわいたので、アーキテクチャパターンのMVCをおさらいしています。概念はわかっても、経験不足ゆえにイマイチ感覚がつかめない。
*1:Quick3(3-way partition)とは、また別物です
