ソフトⅡコース担当 ブログのおにーさまこと高橋です。
平成27年度春期基本情報技術者試験午後問8の解説をしたいと思います。問題は、IPAのサイトをご覧ください。
この問題は、n個のデータの内、k番目に小さな値を求めるというものです。ソートを行うと、k番目に位置する値が求める値となります。もちろんこの方法で問題ありませんが、全体がソートされていなくても、k番目の位置だけが正しくソートされていれば、正しい値を得ることができます。クイックソートは部分的にソートを行うことによって全体をソートする方法なので、k番目付近だけをソートすることができます。
クイックソートは、定めた基準値より大きな値と小さな値に分け、小さいグループはその中で基準値を定めて分ける、大きいグループはその中で基準値を定めて分ける、これを繰り返し範囲を狭めることによって並べ替えます。基準値の選び方や範囲の設定方法により、若干処理手順が異なる場合がありますが、1例を下に例示します。
（図をクリックすると拡大します）
k番目に小さい値は、k番目の位置が正しく並んでいれば求まります。k番目を含む範囲だけをソートすれば十分です。この考えに基づいた問題の処理の流れを図示すると次のようになります。
（図をクリックすると拡大します）
設問1
空欄a、bは上の図に示したTopとLastの変更です。空欄aはア、bはウが入ります。
それでは、続きは次回に
2015年（平成27年度）春期の解説
- 平成27年度 春 基本情報技術者試験 【問13】（その2）
- 平成27年度 春 基本情報技術者試験 【問13】（その1）
- 平成27年度 春 基本情報技術者試験 【問8】（その2）
- 平成27年度 春 基本情報技術者試験 【問8】（その1）
- 平成27年度 春 基本情報技術者試験 【問4】（その2）
- 平成27年度 春 基本情報技術者試験 【問3】
- 平成27年度 春 基本情報技術者試験 【問7】
- 平成27年度 春 基本情報技術者試験 【問4】（その1）
- 平成27年度 春 基本情報技術者試験 【問5】
- 平成27年度 春 基本情報技術者試験 【問1】（その2）
- 平成27年度 春 基本情報技術者試験 【問6】
- 平成27年度 春 基本情報技術者試験 【問1】（その1）
- 平成27年度 春 基本情報技術者試験 【問2】
- Date：
- この記事を
友だちに教える - LINE
- - HatenaBookmark
- GooglePlus
