はじめに
情報処理試験問題でよく登場する整列アルゴリズムの問題。
基本的な整列アルゴリズムには「バブルソート」「選択ソート」「挿入ソート」、そしてより高速な整列アルゴリズムには「シェルソート」「クイックソート」「ヒープソート」「マージソート」などがあります。
スポンサーリンク
本記事では、配列の2分割を繰り返し、その要素を整列しながら戻していく「マージソート」について図解を利用してわかりやすく解説しています。
マージソートとは
マージソートとは、整列対象の値を2分割にしていく操作を繰り返し、要素数が1になるまで細分化、そして細分化した要素同士を整列しながら戻していく手法です。
- 整列対象の値を2分割にする。
- 2分割した値の要素数が1になるまで、2分割を繰り返す。
- 分割した要素同士を並び替えしながら戻していく。
それでは具体的に図解でクイックソートの流れを説明していきます。
暗記ポイント
マージソートとは、要素数が1になるまで2分割を繰り返し、整列しながら戻していく整列アルゴリズム
【手順1】配列の2分割を繰り返して、要素数が1になるまで繰り返す
まずは整列対象の値を2分割していきます。2分割した要素数が1になるまで分割を繰り返していきます。
- 整列対象：「4,3,6,7,1,8,6,2」
- 2分割：「4,3,5,7」「1,8,6,2」
- 更に2分割：「4,3」「5,7」「1,8」「6,2」
- 更に2分割：「4」「3」「5」「7」「1」「8」「6」「2」
要素数が1になったので、ここで2分割の繰り返しは終了です。
【手順2】分割した要素を並び替えしながら戻していく
次に分割した要素を戻していきます。ここでポイントなのは、並び替えをしながら戻していくところです。
- 1要素に分割された値：「4」「3」「5」「7」「1」「8」「6」「2」
- 並び替えしながら戻す：「3,4」「5,7」「1,8」「2,6」
- 並び替えしながら戻す：「3,4,5,7」「1,2,6,8」
- 並び変えしながら戻す：「1,2,3,4,5,6,7,8」
マージソートの説明は以上です。整列アルゴリズムの問題は情報処理試験でよく出題される内容なので、ソートの名前とどんな動きなのかは覚えておくことをお勧めします。
[基本整列アルゴリズム]
[高速整列アルゴリズム]