Skip to content

Instantly share code, notes, and snippets.

@todorok1
Last active Aug 28, 2019
Embed
What would you like to do?
クイックソートアルゴリズムのC#による実装例。
using UnityEngine;
/// <Summary>
/// クイックソートを行うスクリプトです。
/// </Summary>
public class QuickSort : 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);
// クイックソートを行います。
ExecuteQuickSort(targetArray, 0, targetArray.Length - 1);
// コンソールに配列の中身を表示します。
Debug.Log("*** 最終結果 ***");
InspectArrayContents(targetArray);
Debug.Log($"処理回数は {iterationNum} 回、 交換回数は {swapNum} 回でした。");
}
/// <Summary>
/// 引数で渡された値の中から中央値を返します。
/// </Summary>
/// <param id="top">確認範囲の最初の要素</param>
/// <param id="mid">中確認範囲の真ん中の要素</param>
/// <param id="bottom">確認範囲の最後の要素</param>
int GetMediumValue(int top, int mid, int bottom){
if (top < mid){
if (mid < bottom){
return mid;
} else if (bottom < top){
return top;
} else {
return bottom;
}
} else {
if (bottom < mid){
return mid;
} else if (top < bottom){
return top;
} else {
return bottom;
}
}
}
/// <Summary>
/// クイックソートを行います。
/// </Summary>
/// <param id="array">ソート対象の配列</param>
/// <param id="left">ソート範囲の最初のインデックス</param>
/// <param id="right">ソート範囲の最後のインデックス</param>
void ExecuteQuickSort(int[] array, int left, int right){
iterationNum++;
Debug.Log("ExecuteQuickSortが呼ばれました。");
InspectArrayContents(array);
// 確認範囲が1要素しかない場合は処理を抜けます。
if (left >= right){
return;
}
// 左から確認していくインデックスを格納します。
int i = left;
// 右から確認していくインデックスを格納します。
int j = right;
// ピボット選択に使う配列の真ん中のインデックスを計算します。
int mid = (left + right) / 2;
// ピボットを決定します。
int pivot = GetMediumValue(array[i], array[mid], array[j]);
while (true){
// ピボットの値以上の値を持つ要素を左から確認します。
while (array[i] < pivot){
i++;
}
// ピボットの値以下の値を持つ要素を右から確認します。
while (array[j] > pivot){
j--;
}
// 左から確認したインデックスが、右から確認したインデックス以上であれば外側のwhileループを抜けます。
if (i >= j){
break;
}
// そうでなければ、見つけた要素を交換します。
int temp = array[j];
array[j] = array[i];
array[i] = temp;
// 交換を行なった要素の次の要素にインデックスを進めます。
i++;
j--;
// 交換回数を増やします。
swapNum++;
}
InspectArrayContents(array);
Debug.Log($"左側の範囲 {array[left]} から {array[i - 1]} まで / 右側の範囲 {array[j + 1]} から {array[right]} まで");
// 左側の範囲について再帰的にソートを行います。
ExecuteQuickSort(array, left, i - 1);
// 右側の範囲について再帰的にソートを行います。
ExecuteQuickSort(array, j + 1, right);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment