次のプログラムの説明，擬似言語の記述形式の説明及びプログラムを読んで， 設問１，２に答えよ。
〔プログラムの説明〕
整数型の１次元配列Aの A[Min] から A[Max] まで（ 0 ≦Min＜Max）を， クイックソートで整列する副プログラム QuickSort である。
(1) 整列の手順は，次のとおりである。
① A[Min＋1] から A[Max] まで，A[Min] と値が異なる要素を順次探し， 最初に見つかった要素の値と A[Min] の値のうち大きい方を基準値 (Pivot) として選ぶ。 配列の要素がすべて同じ値の場合は，整列処理を終了する。 この基準値を選ぶ処理には，副プログラム FindPivot を用いる。
② Pivot 未満の値の要素がすべて A[Min], … , A[i－1] (Min＜i≦Max) にあり， Pivot 以上の値の要素がすべて A[i], … , A[Max] にあるように要素を並べ替える。 この処理には，副プログラム Arrange を用いる。
③ A[Min], … , A[i－1] と A[i], … , A[Max] をそれぞれ新しい配列とみなして， QuickSortを再帰的に適用して整列する。
(2) 各副プログラムの引数の仕様を表に示す。
表１ QuickSort の引数
| 変数名 | 入力／出力 | 意 味 |
| A | 入出力 | 整列対象の １次元配列 |
| Min | 入力 | 整列する範囲の先頭の要素番号 |
| Max | 入力 | 整列する範囲の最後の要素番号 |
表２ FindPivot の引数
| 変数名 | 入力／出力 | 意 味 |
| A | 入力 | 整列対象の １次元配列 |
| Min | 入力 | 整列する範囲の先頭の要素番号 |
| Max | 入力 | 整列する範囲の最後の要素番号 |
| Ret | 出力 | 基準値が格納されている要素の要素番号を返す。 ただし，A[Min], … , A[Max] がすべて同じ値の場合は，－1を返す。 |
表３ Arrange の引数
| 変数名 | 入力／出力 | 意 味 |
| A | 入出力 | 整列対象の１次元配列 |
| Min | 入力 | 整列する範囲の先頭の要素番号 |
| Max | 入力 | 整列する範囲の最後の要素番号 |
| Pivot | 入力 | 基準値 |
| Ret | 出力 | A[Min], … , A[i－1] の値が Pivot 未満となり， A[i], … , A[Max] の値が Pivot 以上となるように要素を並べ替え，i の値を返す。 |
〔擬似言語の記述形式の説明〕
〔プログラム〕
に入れる正しい答えを，
解答群の中から選べ。
a，b に関する解答群
ア K イ L ウ Max エ Min
c，d に関する解答群
ア Ret ← A[K] イ Ret ← A[Max] ウ Ret ← A[Min]
エ Ret ← K オ Ret ← Max カ Ret ← Min
設問２
整数型の１次元配列要素 A[0] から A[9] までを
QuickSort を用いて整列したときの，引数の内容を表４にまとめた。
表中の に入れる正しい答えを，解答群の中から選べ。
表４ QuickSort の呼出し回数と引数の内容
| 呼出し回数 | A | Min | Max |
| 1 回目 |  |
0 | 9 |
| 2 回目 |  |
0 | 4 |
| 3 回目 |  |
 |
 |
| ： | ： | ： | ： |
| n 回目 |  |
9 | 9 |
e に関する解答群
ア
イ
ウ
エ
f，g に関する解答群
ア 0 イ 1 ウ 2
エ 3 オ 4 カ 5
[←前の問題] [次の問題→] [問題一覧表] [分野別] [基本情報技術者試験TOP ]
