応用情報処理技術者試験　過去問　ソート

令和元年度　秋期　応用情報処理技術者試験　午前　問8
あらためて問題と正解

令和元年度　秋期　応用情報処理技術者試験　午前　問8

問題

分割統治を利用した整列法はどれか。

ア　基数ソート

イ　クイックソート

ウ　選択ソート

エ　挿入ソート

解説

問題文にある「分割統治」と「整列法」を確認しましょう。

最初に、選択肢にもなっていると思われる「整列法」を確認してみます。
整列とは、順番に並べることです。この順番は一定の規則によります。カタカナでは、ソートと呼ばれています。値の小さいものから大きいものに並べるものを昇順(数値が昇っていく)、反対に大きいものから小さいものに並ぶものを降順と言います。

ソートで有名なもは、下のようなものでしょうか。選択肢にあるものもあります。
バブルソート、クイックソート、マージソート、挿入ソート、ヒープソート、選択ソート、シェルソートなどがあります。

バブルソートは、端のものから隣のものと大きさを比較して、求めてる順番に入れ替えることを繰り返す方法です。繰り返すので、回数は多くなります。隣のものと入れ替える様子が泡(バブル)が浮き上がっていくのに例えてれています。逐次添加法に分類されます。

クイックソートは、基準値を決めて、その基準値より大きいものと小さいグループを分けていく方法です。大きいグループ、小さいグループの中でも、それぞれ、基準値を決めて、グループを分けていくということを繰り返し、分けられなくなるまで繰り返すことでソートします。ソートという課題を小さい部分に分けていく方法である、分割統治法に分類されます。

マージソートは、データをグループに分けて、並べ替えていく方法です。並び替える際は、2つのグループの先頭のデータを比較して並び替えます。並び替えを行う際に、正しい順番のものを取り出し、次の比較には、先頭が取り出されたグループは、次のデータが先頭データに入れ替わります。このように2つのグループを比較してマージを繰り返すことで、並べ替えます。こちらも分割統治法に分類されます。

挿入ソートは、先頭データの次のデータから、前に並んでいるデータと比較して、自分がどの位置に入るか比較をして、正しい位置に挿入します。挿入されたら次のデータが前にあるデータを比較して、自分がどの位置に入るか比較して挿入するということを繰り返します。後ろの方のデータが、並び替えられた順番になるときは、比較の回数も多くなります。逐次添加法に分類されます。

ヒープソートは、データ構造の一種であるヒープを利用したソートになります。ヒープとは、データ構造の一種の木構造で、親要素(データ)と子要素が正しく並ぶという条件を満たすものになります。木構造はトーナメントのような構造です。トーナメントと言っても、上位も要素で埋まっている形になります。
1番の親要素(根要素)はヒープなので、並び順で先頭になります。親要素を取り出したら、残ったデータで、ヒープにして、根要素を取り出すということを繰り返して、ソートします。データ構造を利用しています。

選択ヒートは、先頭のデータを残っている全てのデータから選択するソートになります。イメージは１対１を行なって、勝者が次のデータと１対１を繰り返して、最後の勝者が、先頭にふさわしい勝者ということを繰り返していきます。勝者が決まったら、残っているもので、同じように１対１を繰り返していきます。
データの比較が多く、計算量が多いソートで時間がかかります。逐次添加法に分類されます。

シェルソートは、等間隔で離れた要素同士を一つのグループとして、グループ内で挿入ソートを行います。ソートを行う対象が、整列済みに近ければ、高速にソートできます。逐次添加法に分類されます。

出てないソートで、選択肢にあるものがあります。基数ソートです。
基数ソートは、基数でのソートを繰り返す方法です。基数とは、位取り記数法で数値を書き記す際に各桁の重み付けの基本となる数になります。10進数の場合、10となります。10になると位が上がっています。
10進数の場合の、基数ソートでは、まず、1の位で、グループを分けます。次に先頭のグループからデータを確認して、10の位で、グループを移動させます。そして、次には、100の位と繰り返していくことで、ソートをさせます。逐次添加法に分類されます。