はじめに
基本情報技術者試験や応用情報技術者試験でよく出題される整列アルゴリズムの問題。
基本的な整列アルゴリズムには「バブルソート」「選択ソート」「挿入ソート」があり、より高速な整列アルゴリズムには「シェルソート」「クイックソート」「ヒープソート」「マージソート」があります。
スポンサーリンク
本記事では、配列の2分割を繰り返しその要素を整列しながら戻していく「マージソート」について図解で分かりやすく解説しています。
マージソートとは
マージソートとは、整列対象のデータを2分割していく操作を繰り返し、要素数が1になるまで細分化、そして細分化した要素同士を整列しながら戻していく手法です。
マージソートの流れ
- 整列対象のデータを2分割する
- 2分割した値の要素数が1になるまで、2分割を繰り返す
- 分割した要素同士を並び替えしながら戻していく
暗記ポイント
マージソートとは、要素数が1になるまで2分割を繰り返し、整列しながら戻していく整列アルゴリズム
それでは、図を利用してマージソートの流れを説明していきます。
【手順1】2分割を要素数が1になるまで繰り返す
まずは整列対象のデータを2分割していきます。2分割した要素数が1になるまで分割作業を繰り返していきます。
- 整列対象：「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」
- 更に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」
これでマージソートは完了です。
[基本整列アルゴリズム]
[高速整列アルゴリズム]
helpful
この記事は役に立ちましたか？