読者です 読者をやめる 読者になる 読者になる

Compte-rendu de l'étude

年間目標の進捗記録用ブログ。

05-003...整列アルゴリズム

問題

整列アルゴリズムの一つであるクイックソートの記述として、適切なものはどれか。

 

  1. 対象集合から基準となる要素を選び、これよりも大きい要素の集合と小さい要素の集合に分割する。この操作を繰り返すことによって、整列を行う。
  2. 対象集合から最も小さい要素を順次取り出して、整列を行う。
  3. 対象集合から要素を順次取り出し、それまでに取り出した要素の集合に順序関係を保つよう挿入して、整列を行う。
  4. 隣り合う要素を比較し、逆順であれば交換して、整列を行う。

 (平成27年度秋、午前問題、問7)

解説

クイックソートは、対象データから基準になる要素を一つ選んで、それより大きい要素と小さい要素で分け、その中からまた一つ選んで、また大小に分け・・・と繰り返すことによってデータを整列する方法。

 

その他の選択肢

2.は選択ソート

遅いけど実装が簡単なのでよく使われる。これの改良版がヒープソート

 

3.は挿入ソート

これも遅いけど実装が簡単。改良版はシェルソート

マジアカの並べ替え問題でやる感じっぽいので何となく遅そうなのは分かる

 

4.はバブルソート

これも遅いけど、、、どれ見てもこう書いてある。

派生形のヒープソートシェルソートに比べて原始的なアルゴリズムなのか。

 

ヒープソート

選択ソートを、木構造を作ることで効率アップさせたもの。

 

シェルソート

バブルソートと挿入ソートの合わせ技で効率アップさせたもの。

 

 

雑感

数学に関しては数Ⅰに足がかかったところで授業が終わった中卒なので

logとか出てくるともう、自分の学歴をちょっと恨んでしまう笑

 

問題文が見づらいので、ア~エだった選択肢を、インデントしてくれる番号リストにしました。