Last active
August 30, 2019 07:37
-
-
Save todorok1/6015e0eef12896601b131df17bb78841 to your computer and use it in GitHub Desktop.
配列をヒープ構造に変換する処理のC#での実装例。
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using UnityEngine; | |
/// <Summary> | |
/// ヒープソートを行うスクリプトです。 | |
/// </Summary> | |
public class HeapSortPre : SortBase { | |
// 処理回数を保持する変数です。 | |
int iterationNum = 0; | |
// 交換回数を保持する変数です。 | |
int swapNum = 0; | |
void Start(){ | |
// ソートしたい配列を定義します。 | |
int[] targetArray = new int[11]{26, 400, 19, 504, 8, 500, 58, 14, 401, 168, 13}; | |
// コンソールに配列の中身を表示します。 | |
InspectArrayContents(targetArray); | |
// 配列をヒープ構造に変換します。 | |
UpHeap(targetArray); | |
// コンソールに配列の中身を表示します。 | |
Debug.Log("*** 最終結果 ***"); | |
InspectArrayContents(targetArray); | |
Debug.Log($"処理回数は {iterationNum} 回、交換回数は {swapNum} 回でした。"); | |
} | |
/// <Summary> | |
/// 引数の配列をヒープ構造に変換します。 | |
/// </Summary> | |
void UpHeap(int[] array){ | |
// 最初の要素は無条件で根に入るのでインデックス1から処理を行います。 | |
for (int i = 1; i < array.Length; i++){ | |
// 入れ替えが発生したかのフラグです。 | |
bool isChanged = false; | |
// 現在の子要素のインデックスを保持します。 | |
int currentIndex = i; | |
// 確認中のインデックスの要素を表示します。 | |
Debug.Log($"インデックス{i}の {array[i]} を確認します。"); | |
// ヒープのルールを満たすまで入れ替えを行います。 | |
while (true){ | |
// ループの呼ばれた回数を増やします。 | |
iterationNum++; | |
// 親要素のインデックスを取得します。 | |
int parentIndex = Mathf.FloorToInt((currentIndex + 1) / 2) - 1; | |
// 交換フラグをfalseにします。 | |
isChanged = false; | |
// 親要素より子要素の方が大きい場合は入れ替えを行います。 | |
if (array[currentIndex] > array[parentIndex]){ | |
// 要素を入れ替えます。 | |
SwapElement(array, currentIndex, parentIndex); | |
// 交換を行ったので、子要素のインデックスは親要素のインデックスとなります。 | |
currentIndex = parentIndex; | |
// 交換フラグをtrueにします。 | |
isChanged = true; | |
} | |
// 交換が発生しなかった場合、または交換によって根にたどり着いた場合はwhileループを抜けます。 | |
if (!isChanged || currentIndex <= 0){ | |
break; | |
} | |
} | |
// コンソールに配列の中身を表示します。 | |
InspectArrayContents(array); | |
} | |
} | |
/// <Summary> | |
/// 配列要素の交換を行います。 | |
/// </Summary> | |
/// <param id="array">対象の配列</param> | |
/// <param id="targetA">交換する要素のインデックス</param> | |
/// <param id="targetB">交換する要素のインデックス</param> | |
protected void SwapElement(int[] array, int targetA, int targetB){ | |
int temp = array[targetA]; | |
array[targetA] = array[targetB]; | |
array[targetB] = temp; | |
// 交換回数を増やします。 | |
swapNum++; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment