読者です 読者をやめる 読者になる 読者になる

TAMALOG

記すことは生きること。知的欲求の最果てに。

quick sort

Quick Sort

quick sortは、最悪計算量がO(N2)と知られていますが、乱択アルゴリズムにすることで計算量の期待値がO(N*lgN)になります。

乱択クイックソートの実装は、私がネットで見たものだけで、二つの方法がありました。

  • 枢軸(ピボット)をランダムに選ぶ
  • 与えられた数列をシャッフルしたあとに、ピボットを選択する

計算量の観点から、前者のほうが適当だと考えたので、前者で実装しました。本実装では、シンプルなクイックソートにアレンジを施しています。ピボットと同値の数は無視することにして、擬似的な3way partition方式にしています*1

Quick Sortのプログラムです。乱択クイックソート

雑記

ケント・ベック『実装パターン』を読みたかったけど、絶版になっていて買えない。大学図書館にも無かった。今度国会図書館に行って読もう。

友人から「大きめの規模を持つシステム(ゲーム)を作っている」という話を聞いて興味がわいたので、アーキテクチャパターンMVCをおさらいしています。概念はわかっても、経験不足ゆえにイマイチ感覚がつかめない。

*1:Quick3(3-way partition)とは、また別物です