Posted at 2007.08.31,Fri
H19春試験の問11
ええと、ソートアルゴリズムなんて忘れたよ。
C言語を始めたときに、課題としてやったぐらい。
たいていの場合、qsort(callback) で間に合ってたしなぁ。
さて、色々なソート方法がありますが、バブル、選択、挿入、クイック、マージ、ヒープ の 6種類について、考え方をざっくりと読んでおいた方が良さそうです。
このページ ( Akademeia ) が、解りやすくまとまってると思います。
まぁ、興味＋時間があれば、適当にプログラムしてみるのも良いかもしれません。
私としては、 1問しか出題されないだろうし、要点だけで十分かと思います。まぁ、今回の問題のように 平均計算量 と 最大計算量 を覚えておくのが有効でしょう。
n個のデータを整列するとき、比較回数が最悪の場合でO（n＾2）で、最良の場合でO（n）となるものはどれか。
ア：クイックソート イ：単純選択法 ウ：単純挿入法 エ：ヒープソート
ア：クイックソート イ：単純選択法 ウ：単純挿入法 エ：ヒープソート
ええと、ソートアルゴリズムなんて忘れたよ。
C言語を始めたときに、課題としてやったぐらい。
たいていの場合、qsort(callback) で間に合ってたしなぁ。
さて、色々なソート方法がありますが、バブル、選択、挿入、クイック、マージ、ヒープ の 6種類について、考え方をざっくりと読んでおいた方が良さそうです。
このページ ( Akademeia ) が、解りやすくまとまってると思います。
まぁ、興味＋時間があれば、適当にプログラムしてみるのも良いかもしれません。
私としては、 1問しか出題されないだろうし、要点だけで十分かと思います。まぁ、今回の問題のように 平均計算量 と 最大計算量 を覚えておくのが有効でしょう。
| ソート | 平均計算量 | 最大計算量 |
|---|---|---|
| バブルソート | O(ｎ^2) | O(ｎ^2) |
| 選択ソート | O(ｎ^2) | O(ｎ^2) |
| 挿入ソート | O(ｎ) | O(ｎ^2) |
| クイックソート | O(nlogn) | O(ｎ^2) |
| マージソート | O(nlogn) | O(ｎlogn) |
| ヒープソート | O(nlogn) | O(ｎlogn) |
PR
Comments
Post a Comment