忍者ブログ
2ヶ月弱で情報処理試験・ソフトウェア開発技術者に合格します。
★RSS 1.0  ★RSS 2.0
Posted at 2018.08.18,Sat
×

[PR]上記の広告は3ヶ月以上新規記事投稿のないブログに表示されています。新しい記事を書く事で広告が消えます。

Posted at 2007.08.31,Fri
H19春試験の問11

n個のデータを整列するとき、比較回数が最悪の場合でO(n^2)で、最良の場合でO(n)となるものはどれか。

ア:クイックソート イ:単純選択法 ウ:単純挿入法 エ:ヒープソート


ええと、ソートアルゴリズムなんて忘れたよ。
C言語を始めたときに、課題としてやったぐらい。
たいていの場合、qsort(callback) で間に合ってたしなぁ。

さて、色々なソート方法がありますが、バブル選択挿入クイックマージヒープ6種類について、考え方をざっくりと読んでおいた方が良さそうです。

このページ ( Akademeia ) が、解りやすくまとまってると思います。

まぁ、興味+時間があれば、適当にプログラムしてみるのも良いかもしれません。

私としては、 1問しか出題されないだろうし、要点だけで十分かと思います。まぁ、今回の問題のように 平均計算量最大計算量 を覚えておくのが有効でしょう。

ソート平均計算量最大計算量
バブルソートO(n^2)O(n^2)
選択ソートO(n^2)O(n^2)
挿入ソートO(n)O(n^2)
クイックソートO(nlogn)O(n^2)
マージソートO(nlogn)O(nlogn)
ヒープソートO(nlogn)O(nlogn)

PR
Comments
Post a Comment
Name :
Title :
E-mail :
URL :
Comments :
Pass :   Vodafone絵文字 i-mode絵文字 Ezweb絵文字
TrackBack URL
TrackBacks
Welcome ...

 
Ad.
Profile
名前:たびと。
職業:元腐れプログラマ

Template by mavericyard*
忍者ブログ [PR]