ここから本文です

アルゴリズムのマージソートに関する質問です。 配列Aに含まれる数が８個の場合は...

プロフィール画像

ala********さん

2011/2/123:35:50

アルゴリズムのマージソートに関する質問です。
配列Aに含まれる数が８個の場合はマージされる順番などは理解しています。
しかし、配列に含まれる数が９個の場合、１０個の場合などはどのような順番で

マージするのかがわかりません。
下のような図を使って教えていただきたいのですが、どなたかお願いします。

A={ 5 2 4 3 6 9 8 7｝

5 2 4 3|6 9 8 7

5 2|4 3|6 9|8 7

5|2|4|3|6|9|8|7 分割完了

2 5|3 4|6 9|7 8

2 3 4 5|6 7 8 9

2 3 4 5 6 7 8 9 ソート完了
数が８つの場合は上のようになる。
A＝｛5 2 4 3 6 9 8 7 4｝←配列に含まれる数が９個 このような場合は？

この質問は、活躍中のチエリアン・専門家に回答をリクエストしました。

閲覧数：
504
回答数：
2
お礼：
50枚

違反報告

ベストアンサーに選ばれた回答

プロフィール画像

mym********さん

編集あり2011/2/209:57:33

＿＿＿＿＿＿＿＿＿＿＿５ ２ ４ ３ ６ ９ ８ ７ ４
＿＿＿＿＿＿＿５ ２ ４＿＿＿＿３ ６ ＿＿＿＿＿ ９ ８ ７ ４
＿＿＿＿＿５ ２＿＿＿４＿＿＿＿３＿６ ＿＿＿＿＿＿＿＿９ ８＿７ ４
＿＿＿＿＿５＿２ ＜－－－分割完了 （省略）


＿＿＿＿＿２ ５＿＿＿４＿＿＿＿３＿６ ＿＿＿＿＿＿＿＿９ ８＿７ ４
＿＿＿＿＿＿＿２ ４ ５＿＿＿＿３ ６ ＿＿＿＿＿ ８ ９＿４ ７
＿＿＿＿＿＿＿＿＿＿２ ３ ４ ５ ６ ＿＿＿＿＿４ ７ ８ ９
＿＿＿＿＿＿＿＿＿＿＿２ ３ ４ ４ ５ ６ ７ ８ ９＿＜－ソート完了


再帰呼出しのネスト深さの違いから疑問をもたれているのだと思いますが
下図の①～④の順に再帰呼出しの分割が進み

＿＿＿＿＿＿＿＿５ ２ ４＿＿＿＿＿＿Ａ
＿＿＿＿＿＿①／＿＿＿＿＼④
＿＿＿＿＿５ ２＿＿＿＿＿＿４＿＿＿＿Ｂ
＿＿＿②／＿＿＼③
＿＿＿５＿＿＿＿２

②③の呼出しから戻ってＢレベルで ２ ５ にソートして
①の呼出し元に戻り、④の呼出しから戻って
Ａレベルで ２ ４ ５ にソートする
という風に処理が進みます。

違反報告

ベストアンサー以外の回答

1〜1件/1件中

プロフィール画像

kit********さん

2011/2/200:05:37

全ては下記URLに書いてあります
http://www.moon.sannet.ne.jp/okahisa/sort/node16.html

違反報告

この質問につけられたタグ

みんなで作る知恵袋　悩みや疑問、なんでも気軽にきいちゃおう！

Q&Aをキーワードで検索：

Yahoo! JAPANは、回答に記載された内容の信ぴょう性、正確性を保証しておりません。
お客様自身の責任と判断で、ご利用ください。
本文はここまでです このページの先頭へ

「追加する」ボタンを押してください。

閉じる

※知恵コレクションに追加された質問は選択されたID/ニックネームのMy知恵袋で確認できます。

不適切な投稿でないことを報告しました。

閉じる