目次
はじめに
情報処理試験問題でよく登場する整列アルゴリズムの問題。
基本的な整列アルゴリズムには「バブルソート」「選択ソート」「挿入ソート」、そしてより高速な整列アルゴリズムには「シェルソート」「クイックソート」「ヒープソート」「マージソート」などがあります。
本記事では、未整列データを木構造にしてソートしていく「ヒープソート」について図解を利用して、分かりやすく解説していきます。
ヒープソートとは
ヒープソートとは未整列のデータを「順序木」といわれる木構造の構成にして、そこから最大値または最小値を取り出して整列、これを繰り返すことで全体を整列させる手法です。
- 未整列データを木構造にする。
- 木構造の根(ルート)が最大値または最小値になるように並び替えを行う。
- 並び替えが完了した木構造の根(ルート)の値を整列済みデータとする。
- 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"も整列済みデータに追加します。
[基本整列アルゴリズム]
[高速整列アルゴリズム]