目次
はじめに
基本情報技術者試験や応用情報技術者試験でよく出題される整列アルゴリズムの問題。
基本的な整列アルゴリズムには「バブルソート」「選択ソート」「挿入ソート」があり、より高速な整列アルゴリズムには「シェルソート」「クイックソート」「ヒープソート」「マージソート」があります。
本記事では、未整列データを木構造にしてソートしていく「ヒープソート」について図解を利用して分かりやすく解説していきます。
ヒープソートとは
ヒープソートとは未整列のデータを「順序木」といわれる木構造の構成にして、そこから最大値または最小値を取り出して整列、これを繰り返すことで全体を整列させる手法です。
ヒープソートの流れ
- 未整列データを木構造にする
- 木構造の根（ルート）が最大値または最小値になるように並び替えを行う
- 並び替えが完了した木構造の根（ルート）の値を整列済みデータとする
- 処理1～3を繰り返して、すべて整列済みデータになったら終了
暗記ポイント
ヒープソートとは、木構造を利用して並び替えを行う整列アルゴリズム
それでは具体的に図解を利用してヒープソートの流れを説明していきます。今回は木構造の根（ルート）が最大値になるパターンで説明しています。
【手順1】未整列データを木構造にする
未整列データを木構造にします。
【手順2】下から順番に入れ替えを行い、木構造の根（ルート）が最大値になるようにする
まずは一番下の葉から比較
- 一番下の葉である"2"と親の"7"を比較
- ここでは"7"の方が大きいのでそのままとする
次に上のグループを比較
- 次に一つ上のグループである"3"と"7"と"1"を比較
- 3つの中では"7"が一番大きい数値なので、"7"と"3"を入れ替える
次に隣のグループを比較
- 次に隣のグループである"5"と"8"と"6"を比較
- 3つの中では"8"が一番大きい数値なので、"8"と"5"を入れ替える
次に一番上のグループを比較
- 次に一番上のグループである"4"と"7"と"8"を比較
- 3つの中では"8"が一番大きい数値なので、"8"と"4"を入れ替える
根（ルート）が最大値になったので整列済みデータへ追加
これで一番上の根（ルート）が最大値になったので、整列済みデータに最大値の"8"を追加します。
【手順3】再び未整列データを木構造にする
整列済みデータとなった"8"を除いた未整列データで再び木構成を作ります。
この時、一番下の"2"を一番上に持っていきます。
【手順4】手順2と同様に下から順番に入れ替えを行い、木構造の根（ルート）が最大値になるようにする
スポンサーリンク
一番下のグループを比較
- 一番下のグループである"7"と"3"と"1"を比較
- ここでは"7"が一番大きいので、そのままとする
隣のグループを比較
- 次に隣のグループである"4"と"5"と"6"を比較
- 3つの中では"6"が一番大きい数値なので、"6"と"4"を入れ替える
次に一番上のグループを比較
- 次に一番上のグループである"7"と"2"と"6"を比較
- 3つの中では"7"が一番大きい数値なので、"7"と"2"を入れ替える
根（ルート）が最大値になったので整列済みデータへ追加
これで一番上の根（ルート）が最大値になったので、整列済みデータに最大値の"7"を追加します。
【手順5】手順3～手順4を繰り返していく
再び木構成を作り、"6"を整列済みデータへ格納
- 整列済みデータとなった"8"と"7"を除いた未整列データで再び木構成を作る（一番下の"4"を一番上に持っていく）
- 左下のグループ（"3","2","1"）で比較。"3”が一番大きいので、"3”と"2"を入れ替える
- 右下のグループ（"5","6"）で比較。"6"が一番大きいので、そのままとする
- 一番上のグループ（"3","4","6"）で比較。"6"が一番大きいので、"6"と"4"を入れ替える
- 整列済みデータに最大値の"6"を追加する
再び木構成を作り、"5"を整列済みデータへ格納
- 未整列データで再び木構造を作る（一番下の"5"を一番上に持っていく）
- 左下のグループ（"2","3","1"）で比較。"3"が一番大きいのでそのままとする
- 上のグループ（"3","5","4"）で比較。"5"が一番大きいのでそのままとする
- 整列済みデータに最大値の"5"を追加する
再び木構成を作り、"4"を整列済みデータへ格納
- 未整列データで再び木構成を作る（一番下の"1"を一番上に持っていく）
- 左下のグループ（"2","3"）で比較。"3”が一番大きいので、そのままとする
- 一番上のグループ（"3","1","4"）で比較。"4"が一番大きいので、"4"と"1"を入れ替える
- 整列済みデータに最大値の"4"を追加する
スポンサーリンク
再び木構成を作り、"3"を整列済みデータへ格納
- 未整列データで再び木構成を作る（一番下の"2"を一番上に持っていく）
- グループ（"3","2","1"）で比較。"3"が一番大きいので、"3"と"2"を入れ替える
- 整列済みデータに最大値の"3"を追加する
再び木構成を作り、"2"を整列済みデータへ格納
- 未整列データで再び木構成を作る（一番下の"1"を一番上に持っていく）
- グループ（"2","1"）で比較。"2"が一番大きいので、"2"と"1"を入れ替える
- 整列済みデータに最大値の"2"を追加する
最後の"1"を整列済みデータへ格納
最後に残った"1"を整列済みデータに追加すれば完了です。
[基本整列アルゴリズム]
[高速整列アルゴリズム]
この記事は役に立ちましたか？