並べ替えの手間 [GRE CS]

ま、お硬く言うと「ソートアルゴリズムの複雑性」ですね。

つわけで、「GREサブジェクトテストCS分野の問題(PDF)を解こう！」の続き。

ほいで第三問は、「バブルソート、マージソート、ヒープソート、クイックソート、トーナメントソートのうち、実行時間が最悪の場合Θ(n ²)かかるけど、平均ではΘ(n logn )のものは、どれ？」というもの。

これは、まあ、「暗記物」ですね。代表的なソートに関しては、ベストとアベレージとワーストの実行時間を覚えておけ、と。

つわけで、以下に、問題文に挙がっているソートについて、ワーストとアベレージの実行時間を列挙しときます。

ソート名	ワースト	アベレージ
バブル	Θ(n ²)	Θ(n ²)
マージ	Θ(n logn )	Θ(n logn )
ヒープ	Θ(n logn )	Θ(n logn )
クイック	Θ(n ²)	Θ(n logn )

（「トーナメントソート」って聞いたことないんですけど……）

で、これらソートアルゴリズムはけっこう重要だし、それに、アルゴリズムの複雑さがらみの問題も頻出なんで、別項を設けて、それらのことについてあとで書きたいなあ、と思っとります……が、腹減ったんで今はとりあえず飯食います。

では。