Skip to content

Instantly share code, notes, and snippets.

@todorok1
Last active Aug 30, 2019
Embed
What would you like to do?
配列をヒープ構造に変換する処理のC#での実装例。
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