平成14年 春期 基本情報技術者 午後 問04 擬似言語の記述形式

質問

設問２で２回目がなぜ　このような値になるのかが　理解できません

回答No.1

noname#50176 · ベストアンサー

まず、このソートの仕組みを簡単にしてみましょう。
（番目とは何番目の要素かを意味するものです）
１．数値配列の比較元の最小番目と比較先の最小番目＋１～最大番目を比較し、
同じ：比較先の番目を１足して次に進める
比較元＞比較先：比較元をピボットとする
比較元＜比較先：比較先をピボットとする
２．1回目のソートはこのピボット値を基準に
最小＝０／最大＝最大要素数－１
（要素数9個ならNo0からNo8で８が最大値なので－1をします）
３．1回目の結果から得られたピボットを基準に、
４．ピボットより左側をさらに整列、この結果のピボットの結果を
基準に少なくなった要素列の左をさらに整列
５．４を繰り返し整列できなくなったら直前の４に戻り今度は右を
整列、さらに４を繰り返す
６．４、５を繰り返しクイックソートは完了です。

では、トレースチャートで示します
（min=最小番目／max=最大番目／p=ピボット値）

3584069127…開始（min=0/max=9/p=5)3と5の比較で大きい5がピボット
7584069123…3,7 入れ替え．7<3,3>=5 比較不成立で(min=0/max=9)
3584069127…7,3入れ替え．3<5でmin+1,7>=5でmax-1(min=1/max=8)
3284069157…5,2 入れ替え．2<5でmin+1,5>=5でmax-1(min=2/max=7)
3214069857…8,1 入れ替え．1<5でmin+1,8>=5でmax-1(min=3/max=6)
3219064857…4,9 入れ替え．9<5,4>=5 比較不成立で(min=3/max=6)
3214069857…9,4 入れ替え．4<5でmin+1,9>=5でmax-1(min=4/max=5)
3214609857…0,6 入れ替え．min,max変わらず（min=4/max=5)
3214069857…6,0 入れ替え．0<5,6>=5によりmin+1,max-1．（min=5/max=4)…min>max で一旦終了．
よって、3214069857　となります。

お礼

非常に難しいです

補足

3584069127…開始（min=0/max=9/p=5)3と5の比較で大きい5がピボット
7584069123…3,7 入れ替え．7<3,3>=5 比較不成立で(min=0/max=9)
------------------------------------------------------------
すでにここで　理解できなくなってます
なぜ５より小さい３を右へ　５より大きい７を左へと
交換するのかが　わかっていません

５と２の交換は理解できるのですが

回答No.4

noname#50176

＞なぜ５より小さい３を右へ　５より大きい７を左へと…
これは、Arrange 関数のリストですが
（あえて矢印を使っていますが、矢印が文字化けしていたらすみません）

3584069127…開始（Min=0/Max=9/Pivot=5)

元の QuickSort 関数が、“Arrange(A[], Min, Max, Pivot, K)”を呼び出します。
つまり最初は“Arrange(A[], 0, 9, 5, K)”と同じ意味ですね。
K は“Kの値を渡す”のではなく“戻り値を格納する変数のアドレス番地を渡す”と解釈して下さい。
では実際に以下の Arrange を処理していきます。

○副プログラム名：Arrange(A[], Min, Max, Pivot, Ret)　…　１
○整数型：L,R,Tmp　…　２
・L ← Min　…　３
・R ← Max　…　４
■L≦R　…　５
｜・Tmp ← A[L]　…　６
｜・A[L] ← A[R]　…　７
｜・A[R] ← Tmp　…　８
｜■A[L] ＜ Pivot　…　９
｜｜・L ← L + 1　…　１０
｜■
｜■A[R] ≧ Pivot　…　１１
｜｜・R ← R - 1　…　１２
｜■
■
・Ret ← L　…　１３

まず、１の時点で、A[]=ソート配列、Min=0、Max=9、Pivot=5、Ret は不定です。
この時点で、A[]=3584069127
次に、２の時点で、変数を定義、３、４の時点で、L=0、R=9 です
５の時点で、0≦9 で成立していますから、６へ進みます。
６～８の時点で、A[0]とA[9]を入れ替えます。
※９～１２の時点で行う判定より前に強制的に入れ替えるのです。
ですから、
A[]=7584069123 となり、A[0]=7、A[9]=3、に変更されます。
次に９のこの時点では、A[0]＜5、つまり 7＜5 で不成立となり１１へ飛びます。
（ L は１０を飛ばすので変わりません）
次に１１のこの時点では、A[9]≧5、つまり 3≧5 で不成立となりループで５へ飛びます。
（ R は１２を飛ばすので変わりません）
この時点で、A[]=7584069123
５の時点で、0≦9 で成立していますから、６へ進みます。
６～８の時点で、A[0]とA[9]を入れ替えます。
この時点で、A[]=3584069127 元に戻りますね。
次に９のこの時点では、A[0]＜5、つまり 3＜5 で成立となり１０へ進みます。
１０の時点で、L=L+1 つまり、L=0+1=1、ループで９へ戻ります。
９のこの時点では、A[1]＜5、つまり 5＜5 で不成立となり１１へ飛びます。
次に１１のこの時点では、A[9]≧5、つまり 7≧5 で成立となり１２へ進みます。
１２の時点で、R=R-1 つまり、R=9-1=8、ループで１１へ戻ります。
１１のこの時点では、A[8]≧5、つまり 2≧5 で不成立となりループで５へ飛びます。
５の時点で、1≦8 で成立していますから、６へ進みます。
６～８の時点で、A[1]とA[8]を入れ替えます。
A[]=3284069157 ですね。
同様に繰り返していけば
A[]=321406985 になるはずです。

お礼

やっとできました
フローチャートをしっかりみず
説明文のみで解こうとしていたのが
まちがいでした
値とフローがつながりました

回答No.3

noname#50176

すみません。Arannge関数 の部分は以下に訂正して下さい。

１．min番目がmax番目より…
大きければこの関数は終了
同じか大きければ２．へ
（最初は、min番目：0番目、max番目：9番目で２．へ行きますね）
２．min番目の数値とmax番目の数値を入れ替える
３．min番目の数値とピボット値を比較してmin番目の数値が…
ピボット値より小さかったらminを次に進め （min=min+1） ３．へ戻って繰り返す。
ピボット値より大きいか同じであれば４．へ
※これはピボットより左は必ずピボットより小さくなるように
小さくなかった所までminを進めます。
４．max番目の数値とピボット値を比較してmax番目の数値が…
ピボット値より大きいか、同じであればmaxを1つ前に戻し
（max=max-1） ４．へ戻って繰り返す
ピボット値より小さかったら １．へ（ループですね）
※これはピボットより右は必ずピボットより大きくなるように
小さかった所までmaxを戻す（9,8,7…のように逆方向に進める）。
【注意】：３．４．の“同じであれば”とありますが以前のFindPivot関数で
“値が異なれば繰り返し…”によりここで同じになることは
あり得ません。

回答No.2

noname#50176

私も初めてこの問題やったときは20分もかかってしまったので（汗）
実際の変化だけ知ってもらえれば大丈夫です。

3584069127…開始（min=0/max=9/p=5)3と5の比較で大きい5がピボット

FindPivot関数は、
１．min番目とmin+1番目を比較し
値が異なれば内容数値の大きい方の要素番号（何番目かを示す）
２．同じであれば比較対照のmaxを次の要素にして(max=max+1)
１．へ戻り繰り返し、１．で異なっていたらこのFindPivot関数は終了

となり、
最初、min=0,max=9 なので、
A[min]とA[min+1]、つまり A[0]とA[1]を比較。
A[0]=0番目の内容：3　／　A[1]=1番目の内容：5
3<5 で5が大きいので大きいほうの min+1 を返します。
これは K=min+1 と記述されているので、Kを返すわけです。
結果ここでは 1 となります。
この関数から戻ると、（j = 結果の1）pivot=A[j] としているので
pivot=A[1] つまり pivot=5（A[1]の内容が5）でpivotを示す
pは5です。（p はこの回答説明用でpivotと同じです）

続いて、
入れ替え処理のメインとなる Arrange関数は次の流れになります。
１．min番目の数値とmax番目の数値を入れ替える
２．min番目の数値とピボット値を比較してmin番目の数値が…
ピボット値より小さかったらminを次に進め （min=min+1） ２．へ戻って繰り返す。
ピボット値より大きいか同じであれば３．へ
※これはピボットより左は必ずピボットより小さくなるように
小さくなかった所までminを進めます。
３．max番目の数値とピボット値を比較してmax番目の数値が…
ピボット値より大きいか、同じであればmaxを1つ前に戻し
（max=max-1） ３．へ戻って繰り返す
ピボット値より小さかったら ４．へ
※これはピボットより右は必ずピボットより大きくなるように
小さかった所までmaxを戻す（9,8,7…のように逆方向に進める）。
【注意】：３．４．の“同じであれば”とありますが以前のFindPivot関数で
“値が異なれば繰り返し…”によりここで同じになることは
あり得ません。

「言ってることが、解らない！！」
と感じてしまうようであれば、上記のArrange関数の流れと、
回答のNo.1で載せましたトレースチャートと見比べてみてください。

特に「ここが難しい」と感じられましたら気兼ねなく
おっしゃって下さい。