基数整列法について教えてください（後編）

質問

基数整列法について教えてください（前編）の続きです。
長文につき１投稿では入りきらないため、２回にわけております。

回答はこちら（後編）のほうにお願いいたします。

ちゃりお
--------------------------------------------------------------------

【流れ図】
端子：開始
│
処理：３→桁数
│
ループ始端：桁ループ（桁数＝1、桁数）
│
│
　ループ始端：山数クリア（山番号＝０，９）
　│
　処理：０→山数（山番号）
　│
　ループ終端：山数クリア
　│
　│
　ループ始端：分類ループ（番号＝１、件数）
　│
　処理：ユーザ関数（番号、桁）→山番号・・・桁の数字を山番号に設定
　│
　処理：山数（山番号）+１→山数（山番号）／　データ（番号）→山（山番号、山数（山番号））
　│
　ループ終端：分類ループ
　│
　│
　処理：０→番号
　│
　│
　ループ始端：統合ループ（山番号＝０，９）
　│
　│
　　ループ始端：転送ループ（数＝１、山数（山番号））
　　│
　　処理：番号+１→番号／　山（山番号、数）→データ（番号）
　　│
　　ループ終端：転送ループ
　│
　│
　ループ終端：統合ループ
│
│
ループ終端：桁ループ
│
端子：終了

関連URL: http://oshiete1.goo.ne.jp/kotaeru.php3?q=211604

回答No.1

minimum · ベストアンサー

>整列の様子は理解できるのですが
ということなのでいきなり流れ図の説明からします

まず変数の使われかたから

データ(n):
　元々のデータが入っています
　整列後のデータもここに格納されます

山(山番号、山のデータ数):
　整列のためにデータを分類する場所です
　例えば、１桁目の数字で分類時の312は１桁目が２である数の３番目なので
　（いわば「２組の出席番号３番、312君」）

　山(２、３)＝３１２

　となるわけです。

山番号:
　そのデータがどの山に入ればいいかを示す変数です

山数:
　それぞれの山にデータがいくつ入っているかを示しています
　つまり新しいデータを入れるときには

　山数（山番号）+１→山数（山番号）
　と、山数を一つ増やし

　データ（番号）→山（山番号、山数（山番号））
　と、そこにデータを入れればいいわけです

番号:
　データ(n)の何番目を処理中かを示す数です。

では流れ図を見ていきましょう

まず全体が
//////////////////////////////////////
処理：３→桁数
│
ループ始端：桁ループ（桁数＝1、桁数）
//////////////////////////////////////
ループ終端：桁ループ
//////////////////////////////////////
の二つに挟まれています。
これは１桁目・２桁目・３桁目と同じ処理をしているだけです。

次にこの内部の先頭部分
////////////////////////////////////////////////////////////////
ループ始端：山数クリア（山番号＝０，９）
　処理：０→山数（山番号）
ループ終端：山数クリア

ループ始端：分類ループ（番号＝１、件数）
　処理：ユーザ関数（番号、桁）→山番号・・・桁の数字を山番号に設定
　処理：山数（山番号）+１→山数（山番号）
　処理：データ（番号）→山（山番号、山数（山番号））
ループ終端：分類ループ
////////////////////////////////////////////////////////////////
は、データ(n)に入っている数値を全て山に移し替える作業をしています。
山数クリアループは分類ループの前処理として存在します。
これは山数を０にする事により（実際にはデータが残っていたとしても）
山の内部を空にします。

分類ループは全データに対して同じ処理をするループです。
「全データに対し」
「まずユーザ関数でどの山に入ればいいかを求め」
「その山の定員を１増やし」
「最後尾に入れてやる」
「…」
と読んでください。

次に後半部分
/////////////////////////////////////////////////////////////
処理：０→番号

ループ始端：統合ループ（山番号＝０，９）
　ループ始端：転送ループ（数＝１、山数（山番号））
　　処理：番号+１→番号
　　処理：山（山番号、数）→データ（番号）
　ループ終端：転送ループ
ループ終端：統合ループ
//////////////////////////////////////////////////////////////
は、山の値を全てデータ(n)に戻す作業をします。
さっきと同じように番号を０にする事によってデータ(n)は空になりました。

こんどの６行は
「それぞれの山に対して」
「山の先頭から順番に」
「データ(n)の末尾の一個となりに」
「値を書き込んでいく」
「…」
「…」
と読んでください。

お礼

minimumさん、

配列のスケールをずっと小さくして（２１３、１３２、３２１）トレースしたら、並べ替えが成功しました。とりあえず補足でのやり方でいいんですね。たいへん助かりました。ありがとうございます。

ちゃりお

補足

minimumさん、

流れ図の解説、感謝いたします。理解をさらに深めることが出来ました。

４時間理解とトレースで格闘した挙句まだ行き詰まってしまいました（＾＾；どこで考え違いを犯しているのか、指摘いただけないでしょうか？

[データ]６件　※トレース用にデータ数を若干減らしてあります
（１）　（２）　（３）　（４）　（５）　（６）
４２３　１２１　２３１　２３２　２５３　３１２

[分類ループ]
桁ループ　分類ループ　ユーザ関数　山数　　　山
桁数　　　番号　　　　山番号　　　（山番号）（山番号、山数（山番号））
=====================================================================
１　　　　１　　　　　３　　　　　１　　　　４２３　→　山（３，１）
　　　　　２　　　　　１　　　　　２　　　　１２１　→　山（１，２）
　　　　　３　　　　　１　　　　　３　　　　２３１　→　山（１，３）
　　　　　４　　　　　２　　　　　４　　　　２３２　→　山（２，４）
　　　　　５　　　　　３　　　　　５　　　　２５３　→　山（３，５）
　　　　　６　　　　　２　　　　　６　　　　３１２　→　山（２，６）

[統合ループ＆転送ループ]
統合ループ　転送ループ　番号　山（山番号、数）→データ番号
山番号　　　数
=====================================================================
０　　　　　１　　　　　１　　山（０，１）　→　データ　（１）該当なし
　　　　　　２　　　　　２　　山（０，２）　→　データ　（２）該当なし
　　　　　　３　　　　　３　　山（０，３）　→　データ　（３）該当なし
　　　　　　４　　　　　４　　山（０，４）　→　データ　（４）該当なし
　　　　　　５　　　　　５　　山（０，５）　→　データ　（５）該当なし
　　　　　　６　　　　　６　　山（０，６）　→　データ　（６）該当なし
１　　　　　１　　　　　７　　山（１，１）　→　データ　（７）該当なし
　　　　　　２　　　　　８　　山（１，２）　→　データ　（８）１２１
　　　　　　３　　　　　９　　山（１，３）　→　データ　（９）２３１
　　　　　　４　　　　１０　　山（１，４）　→　データ（１０）該当なし
　　　　　　５　　　　１１　　山（１，５）　→　データ（１１）該当なし
　　　　　　６　　　　１２　　山（１，６）　→　データ（１２）該当なし