はじめに
こんにちは。Yuinaです🌰
今日は、基本情報技術者試験のクイックソートの問題（問題はこちら)を解いていきます。よろしくお願いいたします!
選択ソートのイメージを膨らませる☁️
クイックソートはpivotを基準に大きい値と小さい値をグループに分ける処理を行っています。
例として、A= [3,6,2,1,8,4,7,5]の配列を並べ替えていきましょう。
FindPivotメソッドには配列A,最小値Min,最大値Max,配列の中身（添字)を受け取るJが引数として渡されています。
Jが存在している場合、基準値であるPivotに配列AのJ番目の値を入れます。
そしてArrangeメソッドを呼び出し、並べ替えを行います。
一巡目のトレース図はこちらです↑
まだ並べ替えができそうですね。
次は配列を半分に分けて、並べ替えを行います。
配列Aは[3,2,1,4,6,8,7,5]なので、左側が[3,2,1]、右側が[4,6,7,5]ですね。
Pivotはそれぞれ2と6になるので、Arrange(A[],Min,Maax,Pivot,K)の”K”はPivotの新しい場所を示します。
そして、QuickSortの再起呼び出しを行います。
こんな感じでどんどんトレースしていきます。
イメージは膨らみましたか?☁️
過去問に挑戦しよう
さて、ここから問題を解いていきましょう!
まず、疑似言語をいくつかのブロックに分けて、処理の流れを理解していきます。
①TopとLastの初期化
TopとLastの初期化を行います。Topは0,Lastは6ですね。(疑似言語では、”開始値=1″です)
②Pivotと走査用変数の初期化
続いて、Pivotと配列の中の値の大きさを比べるための変数を初期化します。
iは左からの操作用変数で、jは右からの操作用変数です。
③走査
ここで、左右でPivot以上(or以下)はないかを走査します。
④走査終了
操作用変数(iとj)がすれ違った時点で、走査を終了します。
⑤交換
走査の結果から見つけた値同士を交換します。
そして操作用変数を次へ移動させます。
⑥走査範囲の更新
TOPとLASTの値を更新し、走査範囲を狭めていきます。
問題をトレースしたところ下記のようになりました。
1回目の処理
2回目の処理
よって、(a)はTOP=1,LAST= 5でア、(b)はTOP=2,LAST= 5でウが正解になります。
2回目の処理で pivot_pos=3 が目標 k=3 と一致したため、関数は終了し、x[3] の値 2 が返されます。よって、(c)の解はイです。
d は、Partition処理中の while True ループ内で要素が交換された回数です。
総交換回数=(1回目の交換)+(2回目の交換)=3+1=4回なので、(d)の解はエになります。
まとめ
疲れたので、今回の解説は設問2までにします。
ありがとうございました!
