【応用情報】バブルソート、クイックソート等、出題されるデータ整列アルゴリズムを解説

バブルソート

• バブルソートは、隣接する数字を比較して右の方が小さければ入れ替えて昇順に整列させるアルゴリズム

クイックソート

• クイックソートは、基準値を決めて、それより大きい数字のグループと小さい数字のグループに分ける、を繰り返して昇順に整列させるアルゴリズム

他に紹介している整列アルゴリズム(選択肢にはなるけど、答えにはあまりならないアルゴリズム)

• 選択ソート
• 挿入ソート
• マージソート
• ヒープソート

1. 先頭2つの数字を比較する。
2. 右の方が小さければ入れ替える。左の方が小さければそのままにする。
3. 次の2つの数字を比較する。
4. 右の方が小さければ入れ替える。左の方が小さければそのままにする。
5. これを最後まで続けると、一番右が一番大きい数字になる。一番右は確定。
6. ①～⑤を、一番右の数字を除いて行う。右から二番目の数字が二番目に大きい数字になる。右から二番目は確定。
7. これを繰り返すことで、右から大きい数字順に並べていく。

1. 基準値を決める。
2. 基準値より大きい数字と小さい数字をそれぞれグループにする。
3. ②で作ったグループの中で、それぞれ基準値を決める。
4. それぞれのグループ内で基準値より大きい数字と小さい数字のグループを作る。
5. 基準値を決める→グループを作る、を整列するまで繰り返す。

応用情報技術者
午前試験　令和6年度春期問7

整列方法に関するアルゴリズムの記述のうち，バブルソートの記述はどれか。ここで，整列対象は重複のない1から9の数字がランダムに並んでいる数字列とする。

ア　数字列の最後の数字から最初の数字に向かって，隣り合う二つの数字を比較して小さい数字が前に来るよう数字を入れ替える操作を繰り返し行う。

イ　数字列の中からランダムに基準となる数を選び，基準より小さい数と大きい数の二つのグループに分け，それぞれのグループ内も同じ操作を繰り返し行う。

ウ　数字列をほぼ同じ長さの二つの数字列のグループに分割していき，分割できなくなった時点から，グループ内で数字が小さい順に並べる操作を繰り返し行う。

エ　未処理の数字列の中から最小値を探索し，未処理の数字列の最初の数字と入れ替える操作を繰り返し行う。

応用情報技術者
午前試験　令和5年度秋期問6

あるデータ列を整列したら状態0から順に状態1，2，・・・，Nへと推移した。整列に使ったアルゴリズムはどれか。

状態0　3，5，9，6，1，2
状態1　3，5，6，1，2，9
状態2　3，5，1，2，6，9
・
・
・
状態N　1，2，3，5，6，9

応用情報技術者
午前試験　令和5年度春期問7

配列に格納されたデータ2，3，5，4，1に対して，クイックソートを用いて昇順に並び替える。2回目の分割が終わった状態はどれか。ここで，分割は基準値より小さい値と大きい値のグループに分けるものとする。また，分割のたびに基準値はグループ内の配列の左端の値とし，グループ内の配列の値の順番は元の配列と同じとする。

ア　1，2，3，5，4
イ　1，2，5，4，3
ウ　2，3，1，4，5
エ　2，3，4，5，1

応用情報技術者
午前試験　令和4年度秋期問6

未整列の配列A[i]（i=1，2，…，n）を，次の流れ図によって整列する。ここで用いられる整列アルゴリズムはどれか。

応用情報技術者
午前試験　令和3年度秋期問5

バブルソートの説明として，適切なものはどれか。

ア　ある間隔おきに取り出した要素から成る部分列をそれぞれ整列し，更に間隔を詰めて同様の操作を行い，間隔が1になるまでこれを繰り返す。

イ　中間的な基準値を決めて，それよりも大きな値を集めた区分と，小さな値を集めた区分に要素を振り分ける。次に，それぞれの区分の中で同様の操作を繰り返す。

ウ　隣り合う要素を比較して，大小の順が逆であれば，それらの要素を入れ替えるという操作を繰り返す。

エ　未整列の部分を順序木にし，そこから最小値を取り出して整列済の部分に移す。この操作を繰り返して，未整列の部分を縮めていく。