データ列が整列の過程で図のように上から下に推移する整列方法はどれか。ここで、図中のデータ列中の縦の区切り線は、その左右でデータ列が分割されていることを示す。
┌─┬─┬─┬─┬─┬─┬─┬─┐
│６│１│７│３│４│８│２│５│
└─┴─┴─┴─┴─┴─┴─┴─┘
┌───┬───┬───┬───┐
│１ ６│３ ７│４ ８│２ ５│
└───┴───┴───┴───┘
┌───────┬───────┐
│１ ３ ６ ７│２ ４ ５ ８│
└───────┴───────┘
┌───────────────┐
│１ ２ ３ ４ ５ ６ ７ ８│
└───────────────┘
ア クイックソート
イ シェルソート
ウ ヒープソート
エ マージソート
エ
ア クイックソートは、適当な値 (ピボット) を一つ選び、データの先頭からピボット以上の数値を探し、次にデータの末尾からピボット以下の数値を探し、その位置を交換する。
交換すべき数値がなくなれば、ピボットを境界として2つの領域に分け、ピボットの選択と、値の交換を繰り返すソート方法である。
┌─┬─┬─┬─┬─┬─┬─┬─┐
│６│１│７│３│４│８│２│５│
└─┴─┴─┴─┴─┴─┴─┴─┘
┌─┬─┬─┬─┬─┬─┬─┬─┐
│２│１│７│３│４│８│６│５│
└─┴─┴─┴─┴─┴─┴─┴─┘
┌─┬─┬─┬─┬─┬─┬─┬─┐
│２│１│４│３│７│８│６│５│
└─┴─┴─┴─┴─┴─┴─┴─┘
┌───────┬───────┐
│２ １ ４ ３│７ ８ ６ ５│
└───────┴───────┘
┌───────┬───────┐
│２ １ ３ ４│５ ８ ６ ７│
└───────┴───────┘
イ シェルソートは、任意の間隔ごとにソートし、更に間隔を詰めていき、間隔が1になるまで続けるソート方法である。
┌─┬─┬─┬─┬─┬─┬─┬─┐
│６│１│７│３│４│８│２│５│
└─┴─┴─┴─┴─┴─┴─┴─┘
┌─┬─┬─┬─┬─┬─┬─┬─┐
│４│１│７│３│６│８│２│５│
└─┴─┴─┴─┴─┴─┴─┴─┘
┌─┬─┬─┬─┬─┬─┬─┬─┐
│４│１│７│３│６│８│２│５│
└─┴─┴─┴─┴─┴─┴─┴─┘
┌─┬─┬─┬─┬─┬─┬─┬─┐
│２│１│４│３│６│８│７│５│
└─┴─┴─┴─┴─┴─┴─┴─┘
ウ ヒープソートは、2分木を根が最大になるようにソートしていくソート方法である。
配列にして表記すると分かりにくくなる。
エ 正しい。マージソートは、隣り合う配列ごとにソートとマージ (併合) を繰り返すソート方法である。
| 問５ | 目次 | 問７ |