Last active
August 30, 2019 12:46
-
-
Save todorok1/f1283f36e6e1cb5c9393bed0acefe50d 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 HeapSort : SortBase { | |
// 処理回数を保持する変数です。 | |
int iterationNum = 0; | |
// 交換回数を保持する変数です。 | |
int swapNum = 0; | |
void Start(){ | |
ExecuteSort(); | |
} | |
void ExecuteSort(){ | |
// ソートしたい配列を定義します。 | |
int[] targetArray = new int[11]{26, 400, 19, 504, 8, 500, 58, 14, 401, 168, 13}; | |
// コンソールに配列の中身を表示します。 | |
InspectArrayContents(targetArray); | |
Debug.Log("UpHeapを実行します。"); | |
// 配列をヒープ構造に変換します。 | |
UpHeap(targetArray); | |
// コンソールに配列の中身を表示します。 | |
InspectArrayContents(targetArray); | |
Debug.Log("DownHeapを実行します。"); | |
// ヒープ構造の配列を使ってソートします。 | |
DownHeap(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> | |
void DownHeap(int[] array){ | |
// ヒープ領域の後ろから確認を行い、狭めていきます。 | |
for (int i = array.Length - 1; i > 0; i--){ | |
// 確認中のインデックスの要素を表示します。 | |
Debug.Log($"インデックス{i}の {array[i]} を確認します。"); | |
// ヒープ領域の最後尾の要素と根を交換します。 | |
SwapElement(array, i, 0); | |
// 入れ替えが発生したかのフラグです。 | |
bool isChanged = false; | |
// 交換した要素のインデックスを保持します。 | |
int currentIndex = 0; | |
// ヒープのルールを満たすまで交換を行います。 | |
while (true){ | |
// ループの呼ばれた回数を増やします。 | |
iterationNum++; | |
// 子要素のインデックスを取得します。 | |
int childIndex = GetBigChildIndex(array, currentIndex, i); | |
// 子要素が無い場合はwhileループを抜けます。 | |
if (childIndex == -1){ | |
break; | |
} | |
// 交換フラグをfalseにします。 | |
isChanged = false; | |
// 子要素のインデックスが返ってきて、かつ親要素よりも大きい場合は交換を行います。 | |
if (array[childIndex] > array[currentIndex]){ | |
SwapElement(array, childIndex, currentIndex); | |
// 交換した要素のインデックスを保持します。 | |
currentIndex = childIndex; | |
// 交換フラグをtrueにします。 | |
isChanged = true; | |
} | |
// 交換が発生しなかった場合はwhileループを抜けます。 | |
if (!isChanged){ | |
break; | |
} | |
} | |
// コンソールに配列の中身を表示します。 | |
InspectArrayContents(array); | |
} | |
} | |
/// <Summary> | |
/// 確認中のインデックスの要素が持つ子要素で、大きな要素のインデックスを返します。 | |
/// 子要素がない場合は-1を返します。 | |
/// </Summary> | |
int GetBigChildIndex(int[] array, int currentIndex, int heapRange){ | |
// 左の子要素があるか確認します。 | |
int leftChild = (currentIndex + 1) * 2 - 1; | |
// 左の子要素が配列の範囲を超えている場合は右の要素もないので-1を返します。 | |
if (leftChild > heapRange - 1){ | |
return -1; | |
} | |
// 右の子要素があるか確認します。 | |
int rightChild = leftChild + 1; | |
// 右の子要素が配列の範囲を超えている場合は左の子要素を返します。 | |
if (rightChild > heapRange - 1){ | |
return leftChild; | |
} | |
// 左の子要素と右の子要素でより値が大きい方を返します。 | |
if (array[leftChild] > array[rightChild]){ | |
return leftChild; | |
} else { | |
return rightChild; | |
} | |
} | |
/// <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