マージソートは、分割と統合を繰り返しながらデータを整列するアルゴリズムです。今回のプログラムでは、どの部分で実際にデータが整列されているのかを詳しく解説します。
マージソートの基本的な動作
マージソートは以下の手順で動作します。
- 配列を再帰的またはループで分割する
- 分割された配列を小さい順に並べながら統合する
今回のプログラムは、ループを用いてマージソートを実装しています。
実際に配列が整列される箇所
プログラムの中で、実際に配列の整列が行われているのは以下の部分です。
while a_yet == True or b_yet == True:
if b_yet == False or (a_yet == True and b_yet == True and temp[a_idx - span_idx] <= output[b_idx]):
output[write_idx] = temp[a_idx - span_idx]
a_idx += 1
if a_idx >= span_idx + span_size // 2:
a_yet = False
else:
output[write_idx] = output[b_idx]
b_idx += 1
if b_idx >= span_idx + span_size:
b_yet = False
write_idx += 1
この部分では、2つの部分配列を比較しながら統合し、小さい値から順に `output` 配列へ格納することで整列を行っています。
コードの詳細な解説
上記のコードを分解して説明すると。
- `while a_yet == True or b_yet == True:` → 2つの部分配列のうち、いずれかにデータが残っている間はループを続ける
- `if b_yet == False or (a_yet == True and b_yet == True and temp[a_idx – span_idx] <= output[b_idx]):` → 片方の配列が空になったか、または `temp` に格納されたデータが `output` の対応するデータより小さい場合、`output[write_idx]` に `temp[a_idx - span_idx]` の値を代入
- `a_idx += 1` で `a` のインデックスを進める
- `if a_idx >= span_idx + span_size // 2:` → `a` の部分配列が空になったら `a_yet = False` に設定
- それ以外の場合、`output[write_idx] = output[b_idx]` で `b` のデータを `output` に書き込み、`b_idx` を進める
- `if b_idx >= span_idx + span_size:` → `b` の部分配列が空になったら `b_yet = False` に設定
- `write_idx += 1` で書き込み位置を1つ進める
この処理によって、2つの部分配列が比較され、小さい値から順番に `output` 配列へ統合されていきます。
まとめ
今回のマージソートのプログラムでは、配列の整列が `while a_yet == True or b_yet == True:` のループ内で行われています。この処理により、2つの部分配列を比較しながら統合し、最終的にソートされた配列が完成します。マージソートの仕組みを理解し、適切なデータ処理を行うことで、より効率的なアルゴリズムの実装が可能になります。
コメント