T_NAKAの阿房ブログ

アクセスカウンタ

zoom RSS 分割統治法_マージソート(2)

<<   作成日時 : 2016/01/19 00:01   >>

ブログ気持玉 0 / トラックバック 0 / コメント 0

では、マージソートのプログラムを見ていきたいと思います。

画像

このプログラムの前半の関数 \(merge(left,right)\) は前記事で書いたアルゴリズムを示しています。
メイン関数 \(mergesort(L)\) は再帰的プログラムになっていて、2分割を繰り返していきます。まず左側だけで突き進んいくように見え、長さが1になった時点で、関数 \(merge(left,right)\) が作用してソートしながら \(return\) していって、全体がソートマージされていくようです。
この例は \([1,4,3,6,5,2,8,7]\) を分割していって、マージソートしています。

さて、手数の問題になってきますが、2分割していくのはバイナリーサーチの時に求めたように \(O(\log _{2} n)\) です。いっぽう、分割した各段階の全体で、 \(O( n)\) のマージソートの手数が発生するので、トータルでは \(O(n\log _{2} n)\) となるように思われます。
これが \(O(n\log _{2} n)\) の手数のソートプログラムということになりますね。

今日はこの辺で。。

テーマ

関連テーマ 一覧


月別リンク

ブログ気持玉

クリックして気持ちを伝えよう!
ログインしてクリックすれば、自分のブログへのリンクが付きます。
→ログインへ

トラックバック(0件)

タイトル (本文) ブログ名/日時

トラックバック用URL help


自分のブログにトラックバック記事作成(会員用) help

タイトル
本 文

コメント(0件)

内 容 ニックネーム/日時

コメントする help

ニックネーム
本 文
分割統治法_マージソート(2) T_NAKAの阿房ブログ/BIGLOBEウェブリブログ
文字サイズ:       閉じる