前回、①に戻り、論理回路(AND・OR・NANDゲート)を整理しました。今回は、科目Bのアルゴリズムに戻り、前々回のバブルソート・選択ソートよりも効率のよい「クイックソート」と「マージソート」を整理します。
なぜ別のソートも学ぶのか
バブルソートや選択ソートは、仕組みは分かりやすいものの、データの数が増えると、比較や入れ替えの回数が大きく増えてしまうという弱点があります。クイックソートとマージソートは、「データを分割する」という発想を使うことで、より効率よく並べ替えを行う方法です。
クイックソートとは
クイックソートは、配列の中から「基準値(ピボット)」を１つ選び、それより小さい値のグループと、大きい値のグループに分ける、という操作を繰り返す方法です。
例えば「５、２、４、１、３」という配列で、基準値を５とした場合、５より小さい値(２、４、１、３)を左側に、５より大きい値(なし)を右側に集めます。次に、左側のグループの中でも同じように基準値を選び、さらに小さいグループと大きいグループに分けていきます。この「分けて、それぞれの中でまた分ける」という操作を、グループが１つの値になるまで繰り返します。
マージソートとは
マージソートは、配列を半分に分割し続け、それ以上分割できない小さな単位にしたあと、今度は整列させながら結合(マージ)していく方法です。
例えば「５、２、４、１」という配列であれば、まず「５、２」と「４、１」に分割し、それぞれをさらに「５」「２」「４」「１」という単位まで分割します。そこから、隣どうしを比較しながら「２、５」「１、４」のように結合し、最後に「１、２、４、５」という１つの整列済みの配列に結合します。
クイックソートとマージソートの違い
自分は、次のように整理して覚えるようにしています。
- クイックソート:基準値をもとに、大小でグループを分けていく(分割優先)
- マージソート:とにかく半分に分割してから、整列させながら結合する(分割してから統合)
どちらも「分割して整理する」という共通点がありますが、クイックソートは「基準値との比較で分ける」、マージソートは「機械的に半分にしてから結合時に整列させる」という違いがあります。
トレースするときの注意点
クイックソート・マージソートのトレース問題は、バブルソートや選択ソートに比べて、分割の階層が深くなる分、追うのが難しく感じました。自分は、分割の様子を、木構造のように図で描き出しながら、どの段階でどのグループになっているかを確認するようにしています。
学習してみた感想
クイックソートとマージソートは、「分割する」という発想そのものが、以前のバブルソート・選択ソートとは大きく異なり、最初は動作のイメージがつかみにくく感じました。ただ、図で分割の様子を描き出したことで、「なぜ効率がよくなるのか」まで含めて納得しながら理解できました。
次回は、スタックとキューの動作をトレースする方法を整理します。
