- ベストアンサー
基数整列法について教えてください（後編）
- 基数整列法について教えてください（後編）の要約文です。
- 基数整列法には、数字を桁ごとに比較し、大小関係に基づいて整列する処理方法です。
- 詳しい流れ図や関連URLは、こちらのサイトを参考にしてください。
- みんなの回答 （1）
- 専門家の回答
質問者が選んだベストアンサー
>整列の様子は理解できるのですが ということなのでいきなり流れ図の説明からします まず変数の使われかたから データ(n): 元々のデータが入っています 整列後のデータもここに格納されます 山(山番号、山のデータ数): 整列のためにデータを分類する場所です 例えば、１桁目の数字で分類時の312は１桁目が２である数の３番目なので （いわば「２組の出席番号３番、312君」） 山(２、３)＝３１２ となるわけです。 山番号: そのデータがどの山に入ればいいかを示す変数です 山数: それぞれの山にデータがいくつ入っているかを示しています つまり新しいデータを入れるときには 山数（山番号）+１→山数（山番号） と、山数を一つ増やし データ（番号）→山（山番号、山数（山番号）） と、そこにデータを入れればいいわけです 番号: データ(n)の何番目を処理中かを示す数です。 では流れ図を見ていきましょう まず全体が ////////////////////////////////////// 処理：３→桁数 │ ループ始端：桁ループ（桁数＝1、桁数） ////////////////////////////////////// ループ終端：桁ループ ////////////////////////////////////// の二つに挟まれています。 これは１桁目・２桁目・３桁目と同じ処理をしているだけです。 次にこの内部の先頭部分 //////////////////////////////////////////////////////////////// ループ始端：山数クリア（山番号＝０，９） 処理：０→山数（山番号） ループ終端：山数クリア ループ始端：分類ループ（番号＝１、件数） 処理：ユーザ関数（番号、桁）→山番号・・・桁の数字を山番号に設定 処理：山数（山番号）+１→山数（山番号） 処理：データ（番号）→山（山番号、山数（山番号）） ループ終端：分類ループ //////////////////////////////////////////////////////////////// は、データ(n)に入っている数値を全て山に移し替える作業をしています。 山数クリアループは分類ループの前処理として存在します。 これは山数を０にする事により（実際にはデータが残っていたとしても） 山の内部を空にします。 分類ループは全データに対して同じ処理をするループです。 「全データに対し」 「まずユーザ関数でどの山に入ればいいかを求め」 「その山の定員を１増やし」 「最後尾に入れてやる」 「…」 と読んでください。 次に後半部分 ///////////////////////////////////////////////////////////// 処理：０→番号 ループ始端：統合ループ（山番号＝０，９） ループ始端：転送ループ（数＝１、山数（山番号）） 処理：番号+１→番号 処理：山（山番号、数）→データ（番号） ループ終端：転送ループ ループ終端：統合ループ ////////////////////////////////////////////////////////////// は、山の値を全てデータ(n)に戻す作業をします。 さっきと同じように番号を０にする事によってデータ(n)は空になりました。 こんどの６行は 「それぞれの山に対して」 「山の先頭から順番に」 「データ(n)の末尾の一個となりに」 「値を書き込んでいく」 「…」 「…」 と読んでください。
お礼
minimumさん、 配列のスケールをずっと小さくして（２１３、１３２、３２１）トレースしたら、並べ替えが成功しました。とりあえず補足でのやり方でいいんですね。たいへん助かりました。ありがとうございます。 ちゃりお
補足
minimumさん、 流れ図の解説、感謝いたします。理解をさらに深めることが出来ました。 ４時間理解とトレースで格闘した挙句まだ行き詰まってしまいました（＾＾；どこで考え違いを犯しているのか、指摘いただけないでしょうか？ [データ]６件 ※トレース用にデータ数を若干減らしてあります （１） （２） （３） （４） （５） （６） ４２３ １２１ ２３１ ２３２ ２５３ ３１２ [分類ループ] 桁ループ 分類ループ ユーザ関数 山数 山 桁数 番号 山番号 （山番号）（山番号、山数（山番号）） ===================================================================== １ １ ３ １ ４２３ → 山（３，１） ２ １ ２ １２１ → 山（１，２） ３ １ ３ ２３１ → 山（１，３） ４ ２ ４ ２３２ → 山（２，４） ５ ３ ５ ２５３ → 山（３，５） ６ ２ ６ ３１２ → 山（２，６） [統合ループ＆転送ループ] 統合ループ 転送ループ 番号 山（山番号、数）→データ番号 山番号 数 ===================================================================== ０ １ １ 山（０，１） → データ （１）該当なし ２ ２ 山（０，２） → データ （２）該当なし ３ ３ 山（０，３） → データ （３）該当なし ４ ４ 山（０，４） → データ （４）該当なし ５ ５ 山（０，５） → データ （５）該当なし ６ ６ 山（０，６） → データ （６）該当なし １ １ ７ 山（１，１） → データ （７）該当なし ２ ８ 山（１，２） → データ （８）１２１ ３ ９ 山（１，３） → データ （９）２３１ ４ １０ 山（１，４） → データ（１０）該当なし ５ １１ 山（１，５） → データ（１１）該当なし ６ １２ 山（１，６） → データ（１２）該当なし