テーマ：クイックソートによる分割
正解はこちら
解答：ア
[基礎知識・用語のまとめ]
クイックソート・・・対象となるデータ列を基準に従って分割し、分割されたデータ列に対して同様の処理を繰り返してソートを行う方法です。分割統治法によるアルゴリズムの一つで、グループ分けや基準値の選び方にはいくつかの方法があり、通常の場合、プログラムでは再起呼び出しが用いられます。
[解法]
配列に格納されたデータ列を照準に並び替えるために、問題文にある次の三つの条件に従って、分割を進めます。
・分割は基準値より小さい値と大きい値のグループに分ける。
・基準値は分割のたびにグループ内の配列の左端の値とする。
・グループ内の配列の値の順番は元の配列と同じとする。
（初めの配列） ２ ３ ５ ４ １ ：基準となる値
（１回目の分割終了） １｜２｜３ ５ ４
基準値２より小さい値（１）と大きい値（３，５，４）のグループに分けます。
（２回目の分割開始） １｜２｜３ ５ ４
１、２は分割を終了し、（３，５，４）のグループに対して基準値を３として分割を行います。
（２回目の分割終了） １｜２｜３｜５ ４
基準値３より小さい値はなく、大きい値（５, ４）のグループだけを分けます。
したがって、（２回目の分割終了）の状態のデータ列は、１、２、３、５、４となり、選択肢「ア」が正解となります。
[参考]
最後までやった場合は以下のようになる、、、らしい。
（３回目の分割開始） １｜２｜３｜５ ４
１、２、３は分割を終了し、（５、４）のグループに対して、基準値を５として分割を行います。
（３回目の分割終了） １｜２｜３｜４｜５
基準値５より小さい値（４）を分けると全てのデータに対する分割が終了し、昇順に並べ替えられたことがわかります。
利用させていただきました素材へのリンク
うさちゃこちゃんねる様 https://www.youtube.com/channel/UCQcDdg4W6r5OfcB1JTcpABw
コメント