基本情報技術者 2015年 春期 午後 問08

解答の導き方

• 左からは、Pivotより小さい3と5を通過し、$i=3$で止まります。$x[3]=6$はPivotと等しいためです。
• 右からは、$x[7]=1$がPivotより大きくないため、$j=7$で止まります。
• $i<j$なので、$x[3]$と$x[7]$を交換します。配列は「3, 5, 1, 4, 7, 2, 6」になります。
• 次に$i=4、j=6$です。左から4を通過して$i=5$で止まり、右からは2の位置で止まります。そこで$x[5]$と$x[6]$を交換します。配列は「3, 5, 1, 4, 2, 7, 6」になります。
• さらに$i=6、j=5$となります。$i\geqq j$なので、分割のループを抜けます。

• 左からは、$x[1]=3$がPivotより小さくないため、$i=1$で止まります。
• 右からは、$x[5]=2$、$x[4]=4$の順にPivotより大きい値を通過し、$x[3]=1$で止まります。このとき$j=3$です。
• $i<j$なので、$x[1]$と$x[3]$を交換します。配列は「1, 5, 3, 4, 2, 7, 6」になります。交換後は$i=2、j=2$です。
• $x[2]=5$はPivotより小さくないため$i$は進まず、右からも$x[2]=5$がPivotより大きいため、$j$を1まで戻します。$i\geqq j$となるので、分割のループを抜けます。

誤りやすいポイント

• Pivotは選択処理のたびに設定し直します。2回目のPivotは、最初のPivotである6ではなく、現在の$x[3]$の値である1です。
• 配列全体が小さい順に並ぶわけではありません。$k$番目の値が含まれる側だけを次の走査範囲にします。
• TopやLastは、交換した位置ではなく、分割後に$k$番目の値が含まれるグループに合わせて更新します。
• 2回目は「$i\leqq k$」が成り立つためTopを更新します。「$k\leqq j$」は成り立たないので、Lastは更新しません。

FAQ

解答の導き方

誤りやすいポイント

• αは、外側の繰返し1回につき1回実行されます。γの実行回数とは数え方が異なります。
• γは、値が異なるときだけではなく、iがjより小さいときに実行されます。そのため、2と2を交換する場合も1回として数えます。
• iとjが交差した後は、γを実行しません。最後にiがj以上になったときは、内側のループを抜けます。

FAQ

解答の導き方

誤りやすいポイント

• Pivotと同じ値に対して、正しい条件「x[i] ＜ Pivot」なら左側の探索は止まります。「x[i] ≦ Pivot」では止まらず、iがさらに進みます。
• fではiが走査範囲の右端を越えてx[5]を参照しますが、配列自体の要素番号1〜6の範囲内です。走査範囲を越えることと、配列そのものの範囲を越えることは別です。
• fではLastが4のまま変わらず、Topも1のままです。外側の繰返し条件が成り立ち続けるため、処理が終わりません。

FAQ